$\newcommand{\nc}{\newcommand}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Zz}{\mathbb{Z}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\cP}{\mathcal{P}}$ $\nc{\DMO}{\DeclareMathOperator}$ $\DMO{\dom}{dom}$ $\DMO{\rng}{rng}$ $\newcommand{\sns}[2]{\genfrac{\{}{\}}{0pt}{0}{#1}{#2}}$
Equivalence relations are ubiquitous in mathematics (see ADS).
In mathematics, as in real life, we seldom care whether two objects are equal as sets.
Equivalence relation can be viewed a generalization of equality.
We only care whether two objects are "equivalent" (or are equal up to some "equivalence").
An equivalence relation is a relation that is reflexive, symmetric and transitive.
Let $E$ be an equivalence relation on $X$. We say that $x, x' \in X$ are $E$-equivalence if $(x,x') \in E$.
The equality $=_X$ on $X$ (a.k.a $\Delta_X$ the identity relation on $X$).
The relation $X \times X$.
Let $f$ be a function with domain $X$. The relation $\equiv_f$ defined by $x \equiv_f x'$ if and only if $f(x) = f(x')$.
Fix $n \in \Nn$. The relation $\equiv_n$ on $\Zz$ defined by $a \equiv_n b$ if and only $a-b$ is multiple of $n$.
The last relation above is known as congruence modulo $n$. Also, $a \equiv_n b$ is often written as $a \equiv b \pmod{n}$
Let $R,R'$ be relations on $X$. $R'$ is finer than $R$ (or $R'$ refines $R$, or $R'$ is a refinement of $R$) if $R' \subseteq R$.
In other words, $R'$ is finer than $R$ means $a$ and $b$ are related by $R$ whenever they are related by $R'$.
Every equivalence relation on $X$ contains $=_X$ (it is also an equivalence relation on $X$). Hence, $=_X$ is the finest equivalence relation on $X$.
Q. What is the coarsest equivalence relation on $X$?
Exercise
Describe the relations $\equiv_0$ and $\equiv_1$.
Given $m,n \ge 1$, when does $\equiv_n$ refine $\equiv_m$?
Let $E$ be an equivalence relation on $X$ and $x \in X$.
The $E$-equivalence class of $x$, denoted by $[x]_E$ (or simply $[x]$ if $E$ is understood) is the set of elements of $X$ that are $E$-equivalent to $x$.
That is, $$ [x]_E = \{a \in X \colon xEa\} $$
Denoted by $X/E$ the set of $E$-equivalence classes. We call $X/E$ the quotient (set) of $X$ by $E$.
Exercise
Let $[x]_n$ be the $\equiv_n$-equivalence class of $x$. Descibe $[0]_3, [1]_3, [2]_3$ and $[-2]_3$.
Find $\Zz/\equiv_3$. (N.B. $\Zz/\equiv_n$ usually written as $\Zz/n\Zz$.)
Let $f$ be a function on $X$ and $x \in X$. Let $[x]_f$ be the $\equiv_f$ equivalence class of $x$.
Describe $[x]_f$ using of $f$ and $f^{-1}$.
Unless otherwise stated, $E$ is an equivalence relation on $X$.
Proposition 1. $xEx'$ if and only if $[x]_E =[x']_E$.
In other words, two elements of $X$ are $E$-equivalent if and only if their $E$-equivalence classes are the same.
A partition of $X$ is a collection $\mathcal{P}$ of non-empty subsets of $X$ such that
The elements of $\mathcal{P}$ are pairwise disjoint; and
The union of the elements of $\mathcal{P}$ is $X$.
The subsets in $\cP$ are called parts.
Exercise. Which of the following are partitions of $\{1,2,3,...,9\}$, why or why not?
a. $\{ \{1,3,5\},\{2,7,8\}\}$
b. $\{\{1\},\{2,3\},\{4,5,9\},\{6,7,8\}\}$.
c. $\{\emptyset, \{1,2,3\},\{4,8,9\},\{5,6,7\}\}$.
d. $\{\{2,3,5,7\},\{1,9\},\{2,4,6,8\}\}$.
e. $\{1,2,3,4,5,6,7,8,9\}$.
f. $\{\{1,2,3,4,5,6,7,8,9\}\}$.
Proposition 2. $X/E$ is a partition of $X$ for any equivalence relation $E$ on $X$.
Conversely, every partition $\mathcal{P}$ of $X$ gives rise to a relation $\equiv_\cP$ on $X$: $$ x \equiv_{\cP} x' \iff x,x'\ \text{belongs the same part in}\ \cP $$
Exercise.
Check that $\equiv_{\cP}$ is an equivalence relation on $X$.
Find the equivalence relations corresponding to the partitions of $\{1,2,\ldots, 9\}$ in the previous exercise.
Do the exercises in ADS
The number of partitions of a set of size $n$ is $Bell_n$ the $n$-th Bell number.
The number of partitions of a set of size $n$ with $k$ parts, denoted by $\sns{n}{k}$, is a Stirling number of the second kind.
So we have
$$ Bell_n = \sum_{k=1}^{n} \sns{n}{k}$$Let $\equiv_{C}$ be the relation on the collection of functions with domain $X$ given by $f \equiv_C g$ if there is a bijection $s$ from the codomain of $f$ to the codomain of $g$ such that $s\circ f = g$.
Ex. Give a two distinct functions with domain $X = \{0,1,2\}$ but $f \equiv_C g$.
Ex. Check that $\equiv_C$ is an equivalence relation on the class of functions with domain $X$.
There are natural 1-to-1 correspondences between the following three types of objects:
Equivalence relations on $X$ (with $\alpha$ equivalence classes)
Partitions of $X$ (with $\alpha$ parts)
$\equiv_C$-equivalence classes of surjections from $X$ (with codomain of cardinality $\alpha$)
We have already seen the correspondence between equivalence relations on $X$ and partitions of $X$.
Given a sujection $f:X \to Y$, the set $$ F_f :=\{ f^{-1}(y) \colon y \in Y\}$$ is a partition of $X$ (with $|Y|$ parts).
One can check that $F_f = F_g$ if and only if $f \equiv_C g$.
Exercise. Check that an equivalence relation $E$ on $X$ corresponds to the $\equiv_C$-class of the canonical surjection $\pi \colon X \to X/E$.