Much of mathematics is grounded in the study of equivalences, and
order relations.
Lattice theory captures the mathematical structure of order relations. Even though equivalence relations are as ubiquitous in mathematics as order relations, the algebraic structure of equivalences is not as well known as that of orders. The former structure draws primarily on
group theory and, to a lesser extent, on the theory of lattices,
categories, and
groupoids.
Group theory Just as
order relations are grounded in
ordered sets, sets closed under pairwise
supremum and
infimum, equivalence relations are grounded in
partitioned sets, which are sets closed under
bijections that preserve partition structure. Since all such bijections map an equivalence class onto itself, such bijections are also known as
permutations. Hence
permutation groups (also known as
transformation groups) and the related notion of
orbit shed light on the mathematical structure of equivalence relations. Let '~' denote an equivalence relation over some nonempty set
A, called the
universe or underlying set. Let
G denote the set of bijective functions over
A that preserve the partition structure of
A, meaning that for all x \in A and g \in G, g(x) \in [x]. Then the following three connected theorems hold: • ~ partitions
A into equivalence classes. (This is the , mentioned above); • Given a partition of
A,
G is a transformation group under composition, whose orbits are the
cells of the partition; • Given a transformation group
G over
A, there exists an equivalence relation ~ over
A, whose equivalence classes are the orbits of
G. In sum, given an equivalence relation ~ over
A, there exists a
transformation group G over
A whose orbits are the equivalence classes of
A under ~. This transformation group characterisation of equivalence relations differs fundamentally from the way
lattices characterize order relations. The arguments of the lattice theory operations
meet and
join are elements of some universe
A. Meanwhile, the arguments of the transformation group operations
composition and
inverse are elements of a set of
bijections,
A →
A. Moving to groups in general, let
H be a
subgroup of some
group G. Let ~ be an equivalence relation on
G, such that a \sim b \text{ if and only if } a b^{-1} \in H. The equivalence classes of ~—also called the orbits of the
action of
H on
G—are the right
cosets of
H in
G. Interchanging
a and
b yields the left cosets. Related thinking can be found in Rosen (2008: chpt. 10).
Categories and groupoids Let
G be a set and let "~" denote an equivalence relation over
G. Then we can form a
groupoid representing this equivalence relation as follows. The objects are the elements of
G, and for any two elements
x and
y of
G, there exists a unique morphism from
x to
y if and only if x \sim y. The advantages of regarding an equivalence relation as a special case of a groupoid include: • Whereas the notion of "free equivalence relation" does not exist, that of a
free groupoid on a
directed graph does. Thus it is meaningful to speak of a "presentation of an equivalence relation," i.e., a presentation of the corresponding groupoid; • Bundles of groups,
group actions, sets, and equivalence relations can be regarded as special cases of the notion of groupoid, a point of view that suggests a number of analogies; • In many contexts "quotienting," and hence the appropriate equivalence relations often called
congruences, are important. This leads to the notion of an internal groupoid in a
category.
Lattices The equivalence relations on any set
X, when ordered by
set inclusion, form a
complete lattice, called
Con X by convention. The canonical
map ker :
X^
X →
Con X, relates the
monoid X^
X of all
functions on
X and
Con X.
ker is
surjective but not
injective. Less formally, the equivalence relation
ker on
X, takes each function
f :
X →
X to its
kernel ker f. Likewise,
ker(ker) is an equivalence relation on
X^
X. == Equivalence relations and mathematical logic ==