Partial equivalence relation

# Partial equivalence relation

Discussion
 Ask a question about 'Partial equivalence relation' Start a new discussion about 'Partial equivalence relation' Answer questions from other users Full Discussion Forum

Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a partial equivalence relation (often abbreviated as PER) on a set is a relation that is symmetric
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...

and transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

. In other words, it holds for all that:
1. if , then (symmetry)
2. if and , then (transitivity)

If is also reflexive
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

, then is an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

.

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
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

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
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...

and constructive mathematics, particularly to define setoid
Setoid
In mathematics, a setoid is a set equipped with an equivalence relation.Setoids are studied especially in proof theory and in type-theoretic foundations of mathematics. Often in mathematics, when one defines an equivalence relation on a set, one immediately forms the quotient set...

s, 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
if and only if is defined at , is defined at , and

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.