Warning: this note is a mess!
Eq classes are equivalently for:
Redefining identity (ex.
set size → study of
cardinality; fixed difference →
modular arithmetic)
Can be done with setoids / eq rels
Can be done with class representatives
In mathematics there is a common pattern of wanting to take some
set and decompose it into
disjoint subsets (ie, forming a
partition). For instance
We can
split N into
even and odds, writing it as
N={n∈N:n even}+{n∈N:n odd}.
Given a graph
G, we could express it as the union of its
components G=C1∪C2∪⋯
If you like, you could construct
N by starting with the integers
Z and “forgetting” signs. That is, express
Z as the sum
Z={0}+{1,−1}+{2,−2}+⋯; this is in some sense “approximately the same” as
N.
Equivalence relations give the formal tools for doing such contructions.
An
equivalence relation over a
set X is a binary relation
∼ on
X which is:
Reflexive;
a∼a
Symmatric; if
a∼b then
b∼a
Transitive; if
a∼b and
b∼c then
a∼c
Given an equivalence relation
∼, its
equivalence classes are all
sets of the form
{y:y∼x} for some
x∈X.
The equivalence relation axioms guarantee that the collection of such classes form a
partition of
X.
The
set of equivalence classes over
X of
∼ is denoted
X/∼ and called a
quotient set.
Given
x∈X, the expression
[x]∼ denotes the equivalence class of
x, namely
{y:y∼x}.
For some class
C, a member
c∈C is called a
representative of
C.
Take a collection of people and define
p1∼p2 iff p1 and
p2 have the same hair color. Then the equivalence classes
group the people by hair color.
On
C, define
a∼b iff ∣a∣=∣b∣. Then the classes are concentric circles around
0.
Let
E⊆N and
O⊆N repsectively be the
set of
even and
odd integers. We may build the
partition N=E+O By defining
n1∼n2⟺2∣(n2−n1); the resultant classes are exactly
{E,O}.
But it may feel instead more intuitive to do it as follows. Let
r:N→{0,1} be
defined as
r(n)=mod(n,2). Then
E is the subset of
N where
r(n)=0, and
O is the subset of
N where
r(n)=1.
We can do this with the
language of equivalence relations by defining
a∼b⟺r(a)=r(b). Then the classes formed by
∼ are exactly
{E,O}.
This pattern always works. Generally, we can go
back-and-forth between equivalence relations
∼ and “
reduction”
functions r:
Given some
function r:X→R, let
a∼b⟺r(a)=r(b). This is an equivalence relation.
Given some equivalence relation
∼ on
X, define
r:X→P(X) as
r(x)=[x]∼.
In both cases we have that the two constructions are
equivalent in the following senses:
a∼b if and only if r(a)=r(b)
The equivalence classes formed by
∼ are exactly the
sets of the form
{x∈X:r(x)=r0} for some
r0.
A
setoid X is a pair
X=(X,∼) of an
underlying set X and an equivalence relation
∼. Forming quotient
sets can be seen as folding a setoid into a
set; that is, we have
a∼b in (X,∼)⟺a=b in X/∼