Rel, bicategory of relations, allegory
left and right euclidean;
extensional, well-founded relations.
An equivalence relation on a set is a binary relation on that is:
(One can also define it as a relation that is both reflexive and euclidean.) The de Morgan dual of an equivalence relation is an apartness relation.
If is any relation on , there is a smallest equivalence relation containing (noting that an intersection of an arbitrary family of equivalence relations is again such; see also Moore closure), called the equivalence relation generated by .
A set equipped with an equivalence relation can be regarded as a groupoid enriched over the cartesian monoidal category of truth values. Equivalently, it is a groupoid that is 0-truncated. Then the equivalence relation on is a way of making into the set of objects of such a groupoid. Equivalently, a set with an equivalence relation is a (0,1)-category whose each morphism is iso, or a symmetric preordered set.
It may well be useful to consider several possible equivalence relations on a given set. When considering a single equivalence relation once and for all, however, it is common to take the quotient set and use that instead. As a groupoid, any set with an equivalence relation is equivalent to a set in this way (although in the absence of the axiom of choice, it is only a “weak” or ana-equivalence).
A set equipped with an equivalence relation is sometimes called a setoid, although at other times that term is used for a pseudo-equivalence relation instead. This terminology is particularly common in foundations of mathematics where quotient sets don't always exist and the above equivalence to a set cannot be carried out. However, arguably this is a terminological mismatch, and such people should say ‘set’ where they say ‘setoid’ and something else (such as ‘preset’, ‘type’, or ‘completely presented set’) where they say ‘set’. (See Bishop set and page 9 of these lecture notes.)
A partial equivalence relation is a symmetric and transitive relation.
A congruence is a notion of equivalence relation internal to a suitable category.
The generalization of this to (∞,1)-category theory is that of groupoid object in an (∞,1)-category.
For the history of the notion of equivalence relation see this MO discussion.
Last revised on April 12, 2021 at 05:37:05. See the history of this page for a list of all contributions to it.