Partial equivalence relation

From Wikipedia, the free encyclopedia

In mathematics, a partial equivalence relation (often abbreviated as PER) R on a set X is a relation which is symmetric and transitive. In other words, it holds for all a, b and c in X that:

(Symmetry) if a R b then b R a
(Transitivity) if a R b and b R c then a R c

If R is reflexive, then R is an equivalence relation. On the other hand, R could be taken as the empty relation, so that there are PERs that are not equivalence relations.

There is in fact a simple structure to the general PER R on X: it is an equivalence relation on some subset Y of X, such that in the complement of Y no element is related by R to any other. Concretely, let $Y = \{ x \in X | x\,R\,x\}$ . By construction, $R$ is reflexive on $Y$ and therefore an equivalence relation on $Y$ . But if $z \notin Y$ , then there is no $w \in X$ for which z R w; if there were, then by symmetry we would have w R z, which implies z R z by transitivity, contradicting $z \notin Y$ .

[edit] Example

For an example of a PER, consider a set $A$ and a partial function $f$ that is defined on some elements of $A$ but not all. Then the relation $\approx$ defined by

$x \approx y$ if and only if $f$ is defined at both $x$ and $y$ , and $f (x) = f (y)$

is a partial equivalence relation but not an equivalence relation. It possesses the symmetry and transitivity properties, but it is not reflexive since if $f (x)$ is not defined then $x \not\approx x$ -- in fact, for such an $x$ there is no $y \in A$ such that $x \approx y$ . It follows immediately that the subset of $A$ for which $\approx$ is an equivalence relation is precisely the subset on which $f$ is defined.