In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) is a homogeneous binary relation that is symmetric and transitive. If the relation is also reflexive, then the relation is an equivalence relation.
Definition Formally, a relation R {\displaystyle R} on a set X {\displaystyle X} is a PER if it holds for all a , b , c ∈ X {\displaystyle a,b,c\in X} that:
if a R b {\displaystyle aRb} , then b R a {\displaystyle bRa} (symmetry) if a R b {\displaystyle aRb} and b R c {\displaystyle bRc} , then a R c {\displaystyle aRc} (transitivity) Another definition for a partial equivalence relation is that R {\displaystyle R} on a set X {\displaystyle X} is a PER if there is some subset Y {\displaystyle Y} of X {\displaystyle X} such that R ⊆ Y × Y {\displaystyle R\subseteq Y\times Y} and R {\displaystyle R} is an equivalence relation on Y {\displaystyle Y} . The two definitions are seen to be equivalent by taking Y = { x ∈ X ∣ x R x } {\displaystyle Y=\{x\in X\mid x\,R\,x\}} .
Properties and applications The following properties hold for a partial equivalence relation R {\displaystyle R} on a set X {\displaystyle X} :
R {\displaystyle R} is an equivalence relation on the subset Y = { x ∈ X ∣ x R x } ⊆ X {\displaystyle Y=\{x\in X\mid x\,R\,x\}\subseteq X} .
R {\displaystyle R} is difunctional: the relation is the set { ( a , b ) ∣ f a = g b } {\displaystyle \{(a,b)\mid fa=gb\}} for two partial functions f , g : X ⇀ Y {\displaystyle f,g:X\rightharpoonup Y} and some indicator set Y {\displaystyle Y}
R {\displaystyle R} is right Euclidean: For a , b , c ∈ X {\displaystyle a,b,c\in X} , a R b {\displaystyle aRb} and a R c {\displaystyle aRc} implies b R c {\displaystyle bRc}
R {\displaystyle R} is left Euclidean: For a , b , c ∈ X {\displaystyle a,b,c\in X} , b R a {\displaystyle bRa} and c R a {\displaystyle cRa} imply b R c {\displaystyle bRc}
R {\displaystyle R} is quasi-reflexive: If x , y ∈ X {\displaystyle x,y\in X} and x R y {\displaystyle xRy} , then x R x {\displaystyle xRx} and y R y {\displaystyle yRy} . None of these properties alone is sufficient to imply that the relation is a PER. If R {\displaystyle R} is both left and right Euclidean, then R {\displaystyle R} is an equivalence relation, and hence a PER.
In non-set-theory settings In type theory, constructive mathematics and their applications to computer science, constructing analogues of subsets is often problematic—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.
Examples A simple example of a PER that is not an equivalence relation is the empty relation R = ∅ {\displaystyle R=\emptyset } , if X {\displaystyle X} is not empty.
Kernels of partial functions If f {\displaystyle f} is a partial function on a set A {\displaystyle A} , then the relation ≈ {\displaystyle \approx } defined by
… excerpt ends here. Continue reading the full article.
