Partial Equivalence Relation

Definition

A partial equivalence relation on a set $A$ is a binary relation $R:A\to A\to \mathrm{Prop}$ that is symmetric and transitive. Unlike an equivalence relation, it need not be reflexive on all of $A$.

The elements for which reflexivity does hold form the support or domain of definition of the PER:

$$\mathrm{supp}(R)=\{x\in A\mid R(x,x)\}.$$

On this support, a partial equivalence relation behaves exactly like an equivalence relation.

Equivalent Characterisation

A relation $R$ on $A$ is a partial equivalence relation if and only if there is a subset $S\subseteq A$ such that:

• $R$ restricts to an equivalence relation on $S$
• whenever $R(x,y)$ holds, both $x$ and $y$ lie in $S$
• outside $S$, the relation is nowhere inhabited

One may take $S=\mathrm{supp}(R)$. Indeed, if $R(x,y)$ then by symmetry and transitivity we get $R(x,x)$ and $R(y,y)$, so every related element lies in the support.

Interpretation

A partial equivalence relation represents a notion of equality that is only defined on part of the ambient set. Two elements can be compared only when they lie in the support, and there the comparison is equivalence-like.

For this reason, PERs are often used to model partial objects or defined elements up to extensional equality. The quotient of a PER is usually taken to be the set of equivalence classes of its support.

Examples

• Any equivalence relation is a partial equivalence relation.
• If $S\subseteq A$, the identity relation on $S$ extended by false outside $S$ is a partial equivalence relation on $A$.
• In realizability and categorical logic, PERs on a set of codes can be used to represent abstract mathematical objects together with an extensional equality relation.

Related Concepts

• Equivalence Relation
• Symmetric Relation
• Transitive Relation
• Quotient Type