---
tag: 6KK361E3EF
kind: proof
name: Proof of the correspondence between equivalence relations and partitions
msc: ["03E20"]
proves: 074482Q7CD
uses: [0SGTMBEWRF, 082RMRSY26, 09CCE86A6D, 0W4RPA8QH3, 08EJC6Q25H, 0ZVHXDSZC7, 0TB16T2C97, 01HT2CH8BH, 01VG2A0BHW, 0FSNQ0GNCC, 07HF9YCWPP, 0XHDTE5YMZ, 0SJ3RX9TXA, 0J6AKYZQT8]
sources:
  - url: https://en.wikipedia.org/wiki/Partition_of_a_set
    locator: Partitions and equivalence relations
  - url: https://proofwiki.org/wiki/Relation_Induced_by_Partition_is_Equivalence
---

## 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|0SGTMBEWRF]] on $A$, and let $\Pi$ be the set of [[partitions|09CCE86A6D]] of $A$.
2. For $\sim$ in $E$, let $\Phi(\sim) = A/{\sim} = \set{[a] \mid a \in A}$ be the [[quotient set|0ZVHXDSZC7]], where $[a]$ is the [[equivalence class|082RMRSY26]] of $a$.
3. By the theorem that [[equivalence classes form a partition|01HT2CH8BH]], $\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|0W4RPA8QH3]], against the definition of a partition.
6. For $P \in \Pi$, define the [[binary relation|08EJC6Q25H]] $\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|0SJ3RX9TXA]] by the [[axiom of extensionality|0TB16T2C97]]. 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|0XHDTE5YMZ]] 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|07HF9YCWPP]] satisfy $\Psi \circ \Phi = \mathrm{id}_E$ and $\Phi \circ \Psi = \mathrm{id}_\Pi$, where $\mathrm{id}$ is the [[identity function|0FSNQ0GNCC]].
20. By the theorem that a function is [[bijective iff it has a two-sided inverse|01VG2A0BHW]], $\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|0J6AKYZQT8]], $\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$.

## Idea

An equivalence relation is recovered from its classes: two elements are related exactly when they share a class. A partition is recovered from its relation: the class of an element is the block that contains it. So the two constructions undo each other, and that makes each one a bijection.