$\def \N {{ \mathbb N }} \def \Z {{ \mathbb Z }} \def \Q {{ \mathbb Q }} \def \R {{ \mathbb R }} \def \C {{ \mathbb C }} \def \H {{ \mathbb H }} \def \S {{ \mathbb S }} \def \P {{ \mathbb P }} \def \to { \longrightarrow } \def \mapsto { \longmapsto } \def \then { ~ \Longrightarrow ~ } \def \iff { ~ \Longleftrightarrow ~ } \def \and { ~ \wedge ~ } \def \or { ~ \vee ~ } \def \d {{~\rm d}} % We prepend a space to the differential symbol d, for good measure! \def \IFF {{\hskip4pt \sc iff \hskip2pt}} \def \Int {{ \bf Int }} \def \Clo {{ \bf Clo }} \def \Lim {{ \bf Lim }} \def \Dom {{ \bf Dom }} \def \Cod {{ \bf Cod }} \def \Ker {{ \bf Ker }} \def \Img {{ \bf Img }} \def \coKer {{ \bf coKer }} \def \coImg {{ \bf coImg }} \def \rem {{ \hskip4pt \rm rem \hskip4pt }} \def \tab {{ \hskip16pt }}$

# The fundamental theorem of equivalence relations

Equivalence relations are “essentially the same” as partitions. More precisely, every equivalence relation on a set $X$ yields a partition of $X$, and every partition of $X$ yields an equivalence relation on $X$. Our goal here is to prove:

$\tab$ Theorem (the fundamental theorem of equivalence relations). Every equivalence relation yields a partition. Every partition yields an equivalence relation.

This is very surprising, particularly because the definitions of equivalence relation and partition are nothing alike.

$\tab$ Definition. An equivalence relation on a set $X$ is a relation on $X$ that is reflexive, symmetric, and transitive.

$\tab$ Definition. A partition of a set $X$ is a pairwise-disjoint cover of $X$.

What all of this means, we explain in the sequel.

# Every equivalence relation yields a partition. Example

Every equivalence relation $(R, X, X)$ on an arbitrary set $X$ gives rise a partition of $X$, and that partition is the quotient set $X/R$ of all equivalence classes of $R$. This means the cells of the partition are the equivalence classes of $R$.

$\tab$ Example. Let $X$ be the set

$X \hskip8pt := \hskip8pt \{0, 1, 2, 3, 4\},$

let $(R, X, X)$ be the equivalence relation on $X$ whose graph $R$ is given by

$R \hskip8pt := \hskip8pt \{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)\}.$

We’ll show that $R$ gives rise to a specific partition of $X$ that is intimately related to $R$. But first, it’s not clear that $R$ is an equivalence relation, so let’s prove that $R$ satisfies the properties of an equivalence relation. For $R$ to satisfy the properties of an equivalence relation, $R$ must be: $1)$ reflexive, $2)$ symmetric, and $3)$ transitive.
For $R$ be to be reflexive, the following statement must hold: $a$ is $R$-related to $a$ (for arbitrary $a \in X$).
For $R$ be to be symmetric, the following statement must hold: if $a$ is $R$-related to $b$, then $b$ is $R$-related to $a$ (for arbitrary $a,b \in X$).
For $R$ be to be transitive, the following statement must hold: if $a$ is $R$-related to $b$ and $b$ is $R$-related to $c$, then $a$ is $R$-related to $c$ (for arbitrary $a,b,c \in X$).
The equivalence relation $(R, X, X)$ gives rise to two equivalence classes, meaning $X/R$ has two elements. And the equivalence classes of $R$, which are precisely the elements of $X/R$, are the following: $\{0, 1, 2\}$ and $\{3, 4\}$. So, $X/R$ is the set

$X/R \hskip8pt := \hskip8pt \{\{0, 1, 2\}, \{3, 4\}\}.$

Why are the equivalence classes of $R$ the subsets $\{0, 1, 2\} \subseteq X$ and $\{3, 4\} \subseteq X$? To answer this, we can compute the equivalence class $a/R$ of each element $a$ of $X$, also denoted $[a]_R$ or $[a]$, and see that the only results are $\{0, 1, 2\}$ or $\{3, 4\}$.
The equivalence class $0/R$ of $0$ under $R$ is the set of all elements of $X$ that $0$ is $R$-related to. Looking at the definition of $R$, we see that
$0$ is $R$-related to $0$ because $(0, 0) \in R$, and
$0$ is $R$-related to $1$ because $(0, 1) \in R$, and
$0$ is $R$-related to $2$ because $(0, 2) \in R$, and
$0$ is not $R$-related to $3$ because $(0, 3) \notin R$, and
$0$ is not $R$-related to $4$ because $(0, 4) \notin R$.
So, the equivalence class $0/R$ of $0$ under $R$ is the set $\{0, 1, 2\}$, meaning $0/R = \{0, 1, 2\}$.
The equivalence class $1/R$ of $1$ under $R$ is the set of all elements of $X$ that $1$ is $R$-related to. Looking at the definition of $R$, we see that
$1$ is $R$-related to $0$ because $(1, 0) \in R$, and
$1$ is $R$-related to $1$ because $(1, 1) \in R$, and
$1$ is $R$-related to $2$ because $(1, 2) \in R$, and
$1$ is not $R$-related to $3$ because $(1, 3) \notin R$, and
$1$ is not $R$-related to $4$ because $(1, 4) \notin R$.
So, the equivalence class $1/R$ of $1$ under $R$ is the set $\{0, 1, 2\}$, meaning $1/R = \{0, 1, 2\}$.
The equivalence class $2/R$ of $2$ under $R$ is the set of all elements of $X$ that $2$ is $R$-related to. Looking at the definition of $R$, we see that
$2$ is $R$-related to $0$ because $(2, 0) \in R$, and
$2$ is $R$-related to $1$ because $(2, 1) \in R$, and
$2$ is $R$-related to $2$ because $(2, 2) \in R$, and
$2$ is not $R$-related to $3$ because $(2, 3) \notin R$, and
$2$ is not $R$-related to $4$ because $(2, 4) \notin R$.
So, the equivalence class $2/R$ of $2$ under $R$ is the set $\{0, 1, 2\}$, meaning $2/R = \{0, 1, 2\}$.
The equivalence class $3/R$ of $3$ under $R$ is the set of all elements of $X$ that $3$ is $R$-related to. Looking at the definition of $R$, we see that
$3$ is not $R$-related to $0$ because $(3, 0) \notin R$, and
$3$ is not $R$-related to $1$ because $(3, 1) \notin R$, and
$3$ is not $R$-related to $2$ because $(3, 2) \notin R$, and
$3$ is $R$-related to $3$ because $(3, 3) \in R$, and
$3$ is $R$-related to $4$ because $(3, 4) \in R$.
So, the equivalence class $3/R$ of $3$ under $R$ is the set $\{3, 4\}$, meaning $3/R = \{3, 4\}$.
The equivalence class $4/R$ of $4$ under $R$ is the set of all elements of $X$ that $4$ is $R$-related to. Looking at the definition of $R$, we see that
$4$ is not $R$-related to $0$ because $(3, 0) \notin R$, and
$4$ is not $R$-related to $1$ because $(3, 1) \notin R$, and
$4$ is not $R$-related to $2$ because $(3, 2) \notin R$, and
$4$ is $R$-related to $3$ because $(3, 3) \in R$, and
$4$ is $R$-related to $4$ because $(3, 4) \in R$.
So, the equivalence class $4/R$ of $4$ under $R$ is the set $\{3, 4\}$, meaning $4/R = \{3, 4\}$.
This sums up the situation:
$\tab\tab$ $0/R \hskip8pt = \hskip8pt \{0, 1, 2\}$
$\tab\tab$ $1/R \hskip8pt = \hskip8pt \{0, 1, 2\}$
$\tab\tab$ $2/R \hskip8pt = \hskip8pt \{0, 1, 2\}$
$\tab\tab$ $3/R \hskip8pt = \hskip8pt \{3, 4\}$
$\tab\tab$ $4/R \hskip8pt = \hskip8pt \{3, 4\}$
$\tab\tab$ $X/R \hskip8pt = \hskip8pt \{0, 1, 2, 3, 4\}/R \hskip8pt = \hskip8pt \{\{0, 1, 2\}, \{3, 4\}\}.$
And here comes the punchline. The set $\{0, 1, 2\}$ and the set $\{3, 4\}$, which are the elements of the set $X/R$, form a partition $P$ of $X$, so that the set

$P \hskip8pt := \hskip8pt \{\{0, 1, 2\}, \{3, 4\}\}$

is a partition of $X$, because the elements of $P$ are pairwise disjoint (since $\{0, 1, 2\} \cap \{3, 4\} = \{\}$), and $\cup P$ is $X$ (since $\cup P$ is $\cup\{\{0, 1, 2\}, \{3, 4\}\}$, which is $\{0, 1, 2, 3, 4\}$, which is $X$).

So, the equivalence relation $(R, X, X)$ yields a partition of $X$, and this partition is $X/R$. More precisely, the cells of the partition $\{\{0, 1, 2\}, \{3, 4\}\}$ are precisely the equivalence classes of $R$, so that the partition $\{\{0, 1, 2\}, \{3, 4\}\}$ is equal to the quotient set $X/R$, which is the set of all equivalence classes of $R$, which is also the set $\{\{0, 1, 2\}, \{3, 4\}\}$ because the equivalence classes of $R$ are $\{0, 1, 2\}$ and $\{3, 4\}$.
$\tab$ $\square$

# Every equivalence relation yields a partition. Proof

$\tab$ Theorem 1. Let $R$ be an equivalence relation on a set $X$. Now $R$ yields a partition of $X$. More precisely, the equivalence classes of $R$ form a partition of $X$. In other words, if $R$ is an equivalence relation, then the quotient set $X/R$ is a partition of $X$.

$\tab$ Proof. “If $R$ is an equivalence relation, then the quotient set $X/R$ is a partition of $X$”. This is a bold claim, so we better make sure we understand it. If $X$ is a set and $R$ is an equivalence relation, what does $X/R$ look like? Well, $X/R$ is the set of all equivalence classes of $R$. So, every element of the set $X/R$ is a subset of the set $X$. So, $X/R$ is a set of subsets of $X$, and so $X/R$ is a subset of the power set ${ \mathcal P } X$. This means the set $X/R$ is a candidate to be a partition of $X$, because a partition of $X$ must be made up of subsets of $X$. But there’s three more requirements:

$\tab\tab1)$ the [(unary) union](set_theory00.html) $\bigcup X/R$ must be all of $X$,
$\tab\tab2)$ the elements of $X/R$ must all be disjoint with each other (ie. pairwise disjoint), and
$\tab\tab3)$ every element of $X/R$ must be nonempty.
First, we’ll prove two facts:

$\tab\tab1)$ Every element of $X$ is in at least one equivalence class of $R$.
$\tab\tab2)$ Every element of $X$ is in at most one equivalence class of $R$.

Together, $1)$ and $2)$ imply:

$\tab\tab3)$ Every element of $X$ is in exactly one equivalence class of $R$.

And $3)$ implies:

$\tab\tab4)$ The equivalence classes of $R$ form a partition of $X$.

And $4)$ is the desired result.

To prove $1)$, let $a \in X$ be an (arbitrary, but fixed) element of $X$. Since $R$ is an equivalence relation, then in particular $R$ is reflexive. So $a$ is $R$-related to $a$ (by the definition of reflexive), or equivalently $(a, a) \in R$, or equivalently $aRa$.
Recall that $[a]$ is the set of all elements of $X$ that are $R$-related to $a$. Since $a$ is an element of $X$ that is $R$-related to $a$, then $a$ is in $[a]$, by the definition of $[a]$.
So the element $a \in X$ is at least in the equivalence class $[a]$. In particular, the element $a \in X$ is in at least one equivalence class. This proves $1)$.

To prove $2)$, let $a \in X$ be an (arbitrary, but fixed) element of $X$. From $1)$ we know that $a$ is in the equivalence class $[a]$.
Now comes the magic: suppose $a$ is in some other equivalence class, in addition to the equivalence class $[a]$. This equivalence class would be the set of all elements that are $R$-related to some (mysterious) element; we don’t know what this (mysterious) element is, or even if it exists, but let’s call it $b$. To be specific, suppose $a$ is in the equivalence class $[b]$, which is the set of all elements of $X$ that are $R$-related to $b \in X$. (Notice that the element $b \in X$ is not arbitrary, but it’s a very specific element that depends on what $a$ we’ve chosen.) By the definition of $[b]$, we know that $a$ is $R$-related to $b$, because $a$ is in $[b]$. But $R$ is symmetric (because $R$ is an equivalence relation), and this implies that $b$ is also $R$-related to $a$.

Well, this contradicts the assumption that $a$ is in some other equivalence class, which proves that $a$ can’t be in some other equivalence class. More specifically, it proves that, if we dare to dream that $a$ is in some equivalence class $[b]$, then $b$ must actually be $a$ (meaning $b = a$), and so $[b]$ must actually be $[a]$ (meaning $[b] = [a]$).

# Every partition yields an equivalence relation. Example

$\tab$ Example. Let $X$ be the set $\{0, 1, 2, 3, 4\}$, let $P$ be the partition of $X$ given by $P \hskip8pt := \hskip8pt \{\{0, 1, 2\}, \{3, 4\}\}$.

This was an example of a general theorem that applies to all sets and all partitions of sets: every partition $P$ of an arbitrary set $X$ gives rise to an equivalence relation on $X$, and the equivalence classes of that equivalence relation are the cells of the partition $P$.

# Every partition yields an equivalence relation. Proof

$\tab$ Theorem 2. Let $P$ be a partition of a set $X$. Now the partition $P$ induces an equivalence relation on $X$.

$\tab$ Proof. TODO

# The fundamental theorem of equivalence relations

We can now prove:

$\tab$ Theorem (the fundamental theorem of equivalence relations). Every equivalence relation yields a partition. Every partition yields an equivalence relation.

$\tab$ Proof. Theorem $1$ together with theorem $2$ prove this result.
$\tab$ $\square$