Partial equivalence relation

In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) ${\displaystyle R}$ on a set ${\displaystyle X}$ is a binary relation that is symmetric and transitive. In other words, it holds for all ${\displaystyle a,b,c\in X}$ that:

1. if ${\displaystyle aRb}$, then ${\displaystyle bRa}$ (symmetry)
2. if ${\displaystyle aRb}$ and ${\displaystyle bRc}$, then ${\displaystyle aRc}$ (transitivity)

If ${\displaystyle R}$ is also reflexive, then ${\displaystyle R}$ is an equivalence relation.

Properties and applications

In set theory, a relation ${\displaystyle R}$ on a set ${\displaystyle X}$ is a PER if, and only if, ${\displaystyle R}$ is an equivalence relation on the subset ${\displaystyle Y=\{x\in X|x\,R\,x\}\subseteq X}$. By construction, ${\displaystyle R}$ is reflexive on ${\displaystyle Y}$ and therefore an equivalence relation on ${\displaystyle Y}$. Actually, ${\displaystyle R}$ can hold only on elements of ${\displaystyle Y}$: if ${\displaystyle xRy}$, then ${\displaystyle yRx}$ by symmetry, so ${\displaystyle xRx}$ and ${\displaystyle yRy}$ by transitivity, that is, ${\displaystyle x,y\in Y}$. However, given a set ${\displaystyle X}$ and a subset ${\displaystyle Y\subseteq X}$, an equivalence relation on ${\displaystyle Y}$ need not be a PER on ${\displaystyle X}$; for instance, considering the set ${\displaystyle E=\{a,b,c,d\}}$, the relation over ${\displaystyle E}$ characterised by the set ${\displaystyle R=\{a,b,c\}^{2}\cup \{(d,a)\}}$ is an equivalence relation on ${\displaystyle \{a,b,c\}}$ but not a PER on ${\displaystyle E}$ since it is neither symmetric[note 1] nor transitive[note 2] on ${\displaystyle E}$.

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

Each partial equivalence relation is a right Euclidean relation. The contrary does not hold: for example, xRy on natural numbers, defined by 0 ≤ x ≤ y+1 ≤ 2, is right Euclidean, but neither symmetric (since e.g. 2R1, but not 1R2) nor transitive (since e.g. 2R1 and 1R0, but not 2R0). Similarly, each partial equivalence relation is a left Euclidean relation, but not vice versa. Each partial equivalence relation is quasi-reflexive,[1] as a consequence of being Euclidean.

In non-set-theory settings

In type theory, constructive mathematics and their applications to computer science, constructing analogues of subsets is often problematic[2]—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.[3]

Examples

A simple example of a PER that is not an equivalence relation is the empty relation ${\displaystyle R=\emptyset }$, if ${\displaystyle X}$ is not empty.

Kernels of partial functions

If ${\displaystyle f}$ is a partial function on a set ${\displaystyle A}$, then the relation ${\displaystyle \approx }$ defined by

${\displaystyle x\approx y}$ if ${\displaystyle f}$ is defined at ${\displaystyle x}$, ${\displaystyle f}$ is defined at ${\displaystyle y}$, and ${\displaystyle f(x)=f(y)}$

is a partial equivalence relation, since it is clearly symmetric and transitive.

If ${\displaystyle f}$ is undefined on some elements, then ${\displaystyle \approx }$ is not an equivalence relation. It is not reflexive since if ${\displaystyle f(x)}$ is not defined then ${\displaystyle x\not \approx x}$ — in fact, for such an ${\displaystyle x}$ there is no ${\displaystyle y\in A}$ such that ${\displaystyle x\approx y}$. It follows immediately that the largest subset of ${\displaystyle A}$ on which ${\displaystyle \approx }$ is an equivalence relation is precisely the subset on which ${\displaystyle f}$ is defined.

Functions respecting equivalence relations

Let X and Y be sets equipped with equivalence relations (or PERs) ${\displaystyle \approx _{X},\approx _{Y}}$. For ${\displaystyle f,g:X\to Y}$, define ${\displaystyle f\approx g}$ to mean:

${\displaystyle \forall x_{0}\;x_{1},\quad x_{0}\approx _{X}x_{1}\Rightarrow f(x_{0})\approx _{Y}g(x_{1})}$

then ${\displaystyle f\approx f}$ means that f induces a well-defined function of the quotients ${\displaystyle X/\approx _{X}\;\to \;Y/\approx _{Y}}$. Thus, the PER ${\displaystyle \approx }$ 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

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.

Notes

1. ${\displaystyle dRa}$, but not ${\displaystyle aRd}$
2. ${\displaystyle dRa}$ and ${\displaystyle aRb}$, but not ${\displaystyle dRb}$

References

1. Encyclopaedia Britannica (EB); although EB's and Wikipedia's notions of quasi-reflexivity differ in general, they coincide for symmetric relations.
2. https://ieeexplore.ieee.org/document/5135/
3. J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini; Paulo Agliano (eds.). Logic and Algebra. CRC Press. pp. 161–180. ISBN 978-0-8247-9606-8.

• Mitchell, John C. Foundations of programming languages. MIT Press, 1996.
• D.S. Scott. "Data types as lattices". SIAM Journ. Comput., 3:523-587, 1976.