#jsDisabledContent { display:none; } My Account | Register | Help

# Partial equivalence relation

Article Id: WHEBN0003450320
Reproduction Date:

 Title: Partial equivalence relation Author: World Heritage Encyclopedia Language: English Subject: Collection: Mathematical Relations Publisher: World Heritage Encyclopedia Publication Date:

### 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 a R b, then b R a (symmetry)
2. if a R b and b R c, then a R c (transitivity)

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

## Contents

• Properties and applications 1
• Examples 2
• Euclidean parallelism 2.1
• Kernels of partial functions 2.2
• Functions respecting equivalence relations 2.3
• References 3

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

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

### Euclidean parallelism

In the Euclidean plane, two lines m and n are parallel lines when mn = ∅. The symmetry of this relation is obvious and the transitivity can be proven in the Euclidean plane, thus Euclidean parallelism is a partial equivalence relation. Nevertheless, mathematicians developing affine geometry prefer the facility of an equivalence relation and therefore sometimes revise the definition of parallelism to allow a line to be parallel to itself, making the new relation of "affine parallelism" that is a reflexive relation.

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

## References

1. ^ J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini, Paulo Agliano. Logic and Algebra. CRC Press. pp. 161–180.
• Mitchell, John C. Foundations of programming languages. MIT Press, 1996.
• D.S. Scott. "Data types as lattices". SIAM Journ. Comput., 3:523-587, 1976.