# Partial equivalence relation

In mathematics, a **partial equivalence relation** (often abbreviated as **PER**) on a set is a relation that is *symmetric* and *transitive*. In other words, it holds for all that:

If is also reflexive, then is an equivalence relation.

In a set-theoretic context, there is a simple structure to the general PER on : it is an equivalence relation on the subset . ( is the subset of such that in the complement of () no element is related by to any other.) By construction, is reflexive on and therefore an equivalence relation on . Notice that is actually only true on elements of : if , then by symmetry, so and 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 (unless , in which case the empty relation *is* an equivalence relation (and is the only relation on )).

### Kernels of partial functions

For another example of a PER, consider a set and a partial function that is defined on some elements of but not all. Then the relation defined by

is a partial equivalence relation but not an equivalence relation. It possesses the symmetry and transitivity properties, but it is not reflexive since if is not defined then — in fact, for such an there is no such that . (It follows immediately that the subset of for which is an equivalence relation is precisely the subset on which is defined.)

### Functions respecting equivalence relations

Let *X* and *Y* be sets equipped with equivalence relations (or PERs) . For , define to mean:

then means that *f* induces a well-defined function of the quotients . Thus, the PER 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.