In
mathematicsMathematics 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
symmetricIn 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
transitiveIn 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:
- if
, then 
(symmetry)
- if
and 
, then 
(transitivity)
If
is also
reflexiveIn 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 relationIn 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
complementIn 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 scienceComputer 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 theoryIn 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
setoidIn 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.
Reference
See also
- 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...
- Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...