Partition of sums of squares

In mathematics, a partial equivalence relation (often abbreviated as PER) $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.

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|xRx\}\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.

Examples

A simple example of a PER that is not an equivalence relation is the empty relation $R=\mathrm{\varnothing }$ (unless $X=\mathrm{\varnothing }$, 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\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:

$\mathrm{\forall }{x}_0{x}_1,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.

References

• Mitchell, John C. Foundations of programming languages. MIT Press, 1996.

See also

• Equivalence relation
• Binary relation