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 
. By construction, R is reflexive on Y and therefore an equivalence relation on Y. But if 
, then there is no 
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 .
[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 
defined by
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 
-- in fact, for such an x there is no 
such that . It follows immediately that the subset of A for which is an equivalence relation is precisely the subset on which f is defined.
[edit] Uses
PER's are used mainly in computer science, in type theory. They are seldom used, and seldom mentioned, in mathematics.
