Partial equivalence relation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) on a set is a relation that is symmetric and transitive. In other words, it holds for all that:

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

If is also reflexive, then is an equivalence relation.

Properties and applications[edit]

In a set-theoretic context, there is a simple structure to the general PER on : it is an equivalence relation on the subset . ( is the subset of such that in the complement of () no element is related by to any other.) By construction, is reflexive on and therefore an equivalence relation on . Notice that is actually only true on elements of : if , then by symmetry, so and by transitivity. Conversely, given a subset Y of X, any equivalence relation on Y is automatically a PER on X.

PERs are therefore[why?] used mainly in computer science, type theory and constructive mathematics, particularly to define setoids, sometimes called partial setoids. The action of forming one from a type and a PER is analogous to the operations of subset and quotient in classical set-theoretic mathematics.

Every partial equivalence relation is a difunctional relation, but the converse does not hold.

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.[1]

Examples[edit]

A simple example of a PER that is not an equivalence relation is the empty relation (unless , in which case the empty relation is an equivalence relation (and is the only relation on )).

Kernels of partial functions[edit]

For another example of a PER, consider a set and a partial function that is defined on some elements of but not all. Then the relation defined by

if and only if is defined at , is defined at , and

is a partial equivalence relation but not an equivalence relation. It possesses the symmetry and transitivity properties, but 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 subset of for 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]

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

References[edit]

  1. ^ J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini, Paulo Agliano. Logic and Algebra. CRC Press. pp. 161–180. ISBN 978-0-8247-9606-8. 

See also[edit]