Partial equivalence relation

(Redirected from )

In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation[1]) is a homogeneous binary relation that is symmetric and transitive. If the relation is also reflexive, then the relation is an equivalence relation.

Definition

edit

Formally, a relation   on a set   is a PER if it holds for all   that:

  1. if  , then   (symmetry)
  2. if   and  , then   (transitivity)

Another more intuitive definition is that   on a set   is a PER if there is some subset   of   such that   and   is an equivalence relation on  . The two definitions are seen to be equivalent by taking  .[2]

Properties and applications

edit

The following properties hold for a partial equivalence relation   on a set  :

  •   is an equivalence relation on the subset  .[note 1]
  • difunctional: the relation is the set   for two partial functions   and some indicator set  
  • right and left Euclidean: For  ,   and   implies   and similarly for left Euclideanness   and   imply  
  • quasi-reflexive: If   and  , then   and  .[3][note 2]

None of these properties is sufficient to imply that the relation is a PER.[note 3]

In non-set-theory settings

edit

In type theory, constructive mathematics and their applications to computer science, constructing analogues of subsets is often problematic[4]—in these contexts PERs are therefore more commonly used, particularly to define setoids, sometimes called partial setoids. Forming a partial setoid from a type and a PER is analogous to forming subsets and quotients in classical set-theoretic mathematics.

The algebraic notion of congruence can also be generalized to partial equivalences, yielding the notion of subcongruence, i.e. a homomorphic relation that is symmetric and transitive, but not necessarily reflexive.[5]

Examples

edit

A simple example of a PER that is not an equivalence relation is the empty relation  , if   is not empty.

Kernels of partial functions

edit

If   is a partial function on a set  , then the relation   defined by

  if   is defined at  ,   is defined at  , and  

is a partial equivalence relation, since it is clearly symmetric and transitive.

If   is undefined on some elements, then   is not an equivalence relation. It is not reflexive since if   is not defined then   — in fact, for such an   there is no   such that  . It follows immediately that the largest subset of   on which   is an equivalence relation is precisely the subset on which   is defined.

Functions respecting equivalence relations

edit

Let X and Y be sets equipped with equivalence relations (or PERs)  . For  , define   to mean:

 

then   means that f induces a well-defined function of the quotients  . Thus, the PER   captures both the idea of definedness on the quotients and of two functions inducing the same function on the quotient.

Equality of IEEE floating point values

edit

The IEEE 754:2008 standard for floating-point numbers defines an "EQ" relation for floating point values. This predicate is symmetric and transitive, but is not reflexive because of the presence of NaN values that are not EQ to themselves.[6]

Notes

edit
  1. ^ By construction,   is reflexive on   and therefore an equivalence relation on  .
  2. ^ This follows since if  , then   by symmetry, so   and   by transitivity. It is also a consequence of the Euclidean properties.
  3. ^ For the equivalence relation, consider the set   and the relation  .   is an equivalence relation on   but not a PER on   since it is neither symmetric ( , but not  ) nor transitive (  and  , but not  ). For Euclideanness, xRy on natural numbers, defined by 0 ≤ xy+1 ≤ 2, is right Euclidean, but neither symmetric (since e.g. 2R1, but not 1R2) nor transitive (since e.g. 2R1 and 1R0, but not 2R0).

References

edit
  1. ^ Scott, Dana (September 1976). "Data Types as Lattices". SIAM Journal on Computing. 5 (3): 560. doi:10.1137/0205037.
  2. ^ Mitchell, John C. (1996). Foundations for programming languages. Cambridge, Mass.: MIT Press. pp. 364–365. ISBN 0585037892.
  3. ^ Encyclopaedia Britannica (EB); although EB's notion of quasi-reflexivity is Wikipedia's notion of left quasi-reflexivity, they coincide for symmetric relations.
  4. ^ Salveson, A.; Smith, J.M. (1988). "The strength of the subset type in Martin-Lof's type theory". [1988] Proceedings. Third Annual Information Symposium on Logic in Computer Science. pp. 384–391. doi:10.1109/LICS.1988.5135. ISBN 0-8186-0853-6. S2CID 15822016.
  5. ^ J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini; Paulo Agliano (eds.). Logic and Algebra. CRC Press. pp. 161–180. ISBN 978-0-8247-9606-8.
  6. ^ Goldberg, David (1991). "What Every Computer Scientist Should Know About Floating-Point Arithmetic". ACM Computing Surveys. 23 (1): 5–48. doi:10.1145/103162.103163. See page 33.