Past exam of the mathematics course of the University of Cambridge / 2015 / ia / Paper 4 / 5E / i / Solution

For an equivalence relation $\sim$ on $X$, the equivalence class of $x\in X$ is $[x]=\{y\in X:y\sim x\}$. A set partition is a family of nonempty, pairwise disjoint subsets whose union is $X$.

Reflexivity ensures $x\in [x]$, so every equivalence class is nonempty and every element belongs to one. If $[x]\cap [y]$ contains $z$, then $z\sim x$ and $z\sim y$; symmetry and transitivity give $x\sim y$. If $w\in [x]$, transitivity gives $w\sim y$, so $w\in [y]$; interchanging $x,y$ gives the reverse inclusion. Thus intersecting equivalence classes are equal.

Taking the collection of distinct equivalence classes therefore produces a set partition of $X$. Every element lies in exactly one class. If $X$ is empty, the empty family is its set partition.