Partial equivalence relation

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:

if $a R b$ , then $b R a$ (symmetry)
if $a R b$ and $b R c$ , then $a R c$ (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 | 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 $x R y$ , then $y R x$ by symmetry, so $x R x$ and $y R y$ 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.

1 Examples
- 1.1 Kernels of partial functions
- 1.2 Functions respecting equivalence relations
2 Reference
3 See also

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.

Reference

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

Partial equivalence relation -- Please Click to Return to Front Page