Proof of the correspondence between equivalence relations and partitions

Proof

We build the map in both directions and check that the two composites are identity functions.

1. Let $A$ be a set. Let $E$ be the set of equivalence relations on $A$, and let $\Pi$ be the set of partitions of $A$.
2. For $\sim$ in $E$, let $\Phi(\sim) = A/{\sim} = \set{[a] \mid a \in A}$ be the quotient set, where $[a]$ is the equivalence class of $a$.
3. By the theorem that equivalence classes form a partition, $\Phi(\sim) \in \Pi$. So $\Phi$ is a function from $E$ to $\Pi$.
4. Let $P \in \Pi$. Each $a \in A$ lies in some block, because the union of the blocks is $A$.
5. In step 4, $a$ lies in only one block. Indeed, if $a \in B_1 \cap B_2$ for blocks $B_1 \neq B_2$, then $B_1$ and $B_2$ are not disjoint, against the definition of a partition.
6. For $P \in \Pi$, define the binary relation $\sim_P$ on $A$ by $a \sim_P b$ when some block of $P$ contains both $a$ and $b$.
7. The relation $\sim_P$ is reflexive. By step 4, each $a$ lies in some block, which contains both $a$ and $a$.
8. The relation $\sim_P$ is symmetric, because the condition in step 6 does not depend on the order of $a$ and $b$.
9. The relation $\sim_P$ is transitive. Let $a \sim_P b$ and $b \sim_P c$, with $a, b \in B_1$ and $b, c \in B_2$ for blocks $B_1, B_2$. By step 5, $b$ lies in only one block, so $B_1 = B_2$. Then $a, c \in B_1$, so $a \sim_P c$.
10. By steps 7 to 9, $\sim_P \in E$. Let $\Psi(P) = \sim_P$. So $\Psi$ is a function from $\Pi$ to $E$.
11. Let $\sim$ be in $E$, and write $\approx$ for $\Psi(\Phi(\sim))$. So $a \approx b$ when some class $[c]$ contains both $a$ and $b$.
12. If $a \sim b$, then $a \in [b]$. By reflexivity, $b \in [b]$. So the class $[b]$ contains both, and $a \approx b$.
13. If $a \approx b$, then $a, b \in [c]$ for some $c$, so $a \sim c$ and $b \sim c$. By symmetry, $c \sim b$. By transitivity, $a \sim b$.
14. By steps 12 and 13, $\approx$ and $\sim$ contain the same pairs. As subsets of $A \times A$, they are equal sets by the axiom of extensionality. So $\Psi(\Phi(\sim)) = \sim$ for each $\sim$ in $E$.
15. Let $P \in \Pi$. For $a \in A$, let $B_a$ be the unique block of $P$ that contains $a$, given by steps 4 and 5. Write $[a]_P$ for the class of $a$ under $\sim_P$.
16. In step 15, $x \sim_P a$ holds exactly when some block contains $x$ and $a$. By step 5, the only block containing $a$ is $B_a$. So $x \sim_P a$ holds exactly when $x \in B_a$. Hence $[a]_P = B_a$.
17. By step 16, $\Phi(\Psi(P)) = \set{[a]_P \mid a \in A} = \set{B_a \mid a \in A}$. Each $B_a$ is a block of $P$, so $\Phi(\Psi(P)) \subseteq P$.
18. Let $B \in P$. Blocks are nonempty, so pick $b \in B$. By step 5, $B = B_b$, so $B \in \Phi(\Psi(P))$. Hence $P \subseteq \Phi(\Psi(P))$, and $\Phi(\Psi(P)) = P$.
19. Two functions with the same domain and the same value at each point have the same pairs, so they are equal. By steps 14 and 18, the compositions satisfy $\Psi \circ \Phi = \mathrm{id}_E$ and $\Phi \circ \Psi = \mathrm{id}_\Pi$, where $\mathrm{id}$ is the identity function.
20. By the theorem that a function is bijective iff it has a two-sided inverse, $\Phi$ is a bijection from $E$ to $\Pi$.
21. Let $\Phi^{-1}$ be the inverse of the bijection $\Phi$, so $\Phi^{-1} \circ \Phi = \mathrm{id}_E$. By step 19 and the associativity of composition, $\Phi^{-1} = \Phi^{-1} \circ (\Phi \circ \Psi) = (\Phi^{-1} \circ \Phi) \circ \Psi = \Psi$. So the inverse sends each partition $P$ to $\sim_P$.