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:

1. if $aRb$, then $bRa$ (symmetry)
2. 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. Hence, in set theory one typically studies the equivalence relation associated with a PER, rather than the PER itself.

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

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.

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

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

See also

• Equivalence relation
• Binary relation