Partial equivalence relation

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

if $aRb$ , then $bRa$ (symmetry)
if $aRb$ and $bRc$ , then $aRc$ (transitivity)

If $R$ is also reflexive, then $R$ is an equivalence relation.

Properties and applications

In a set-theoretic context, there is a simple structure to the general PER $R$ on $X$ : it is an equivalence relation on the subset $Y=\{x\in X|x\,R\,x\}\subseteq X$ . ( $Y$ is the subset of $X$ such that in the complement of $Y$ ( $X\setminus Y$ ) no element is related by $R$ to any other.) By construction, $R$ is reflexive on $Y$ and therefore an equivalence relation on $Y$ . Notice that $R$ is actually only true on elements of $Y$ : if $xRy$ , then $yRx$ by symmetry, so $xRx$ and $yRy$ by transitivity. Conversely, given a subset Y of X, any equivalence relation on Y is automatically a PER on X.

PERs are therefore used mainly in computer science, type theory and constructive mathematics, particularly to define setoids, sometimes called partial setoids. The action of forming one from a type and a PER is analogous to the operations of subset and quotient in classical set-theoretic mathematics.

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

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.^[1]

Examples

A simple example of a PER that is not an equivalence relation is the empty relation $R=\emptyset$ (unless $X=\emptyset$ , in which case the empty relation is an equivalence relation (and is the only relation on $X$ )).

Kernels of partial functions

For another 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

x

f

is defined at

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.)

Functions respecting equivalence relations

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

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

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

References

↑ J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini, Paulo Agliano. 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.