partition is equivalent to an equivalence relation

Proposition 1.

There is a one-to-one correspondence between the set $\operatorname{Part}(S)$ of partitions of $S$ and the set $\operatorname{Equiv}(S)$ of equivalence relations on $S$.

Proof.

Let $S$ be a set.

Suppose $P=\{P_{i}\mid i\in I\}$ is a partition of $S$. Form $E=\bigcup\{P_{i}\times P_{i}\mid i\in I\}$. Given any $a\in S$, $a\in P_{i}$ for some $i\in I$. Then $(a,a)\in P_{i}\times P_{i}\in E$. If $(a,b)\in E$, then $(a,b)\in P_{i}\times P_{i}$ for some $i\in I$, so $a,b\in P_{i}$, whence $(b,a)\in P_{i}\times P_{i}\subseteq E$. Finally, suppose $(a,b),(b,c)\in E$. Then $(a,b)\in P_{i}\times P_{i}$ and $(b,c)\in P_{j}\times P_{j}$, or $a,b\in P_{i}$ and $b,c\in P_{j}$. Since $b\in P_{i}\cap P_{j}$, $P_{i}=P_{j}$ since $P$ is a partition. So $a,c\in P_{i}=P_{j}$, or $(a,c)\in P_{i}\times P_{i}\subseteq E$.

Conversely, suppose $E$ is an equivalence relation on $S$. For each $a\in S$, define

 $[a]=\{b\in S\mid(a,b)\in E\}.$

Then each $a\in[a]$ since $E$ is reflexive. If $b\in[a]$, then $(a,b)\in E$ or $(b,a)\in E$ as $E$ is symmetric. So $a\in[b]$ as well. Next, pick any $c\in[b]$. Then $(b,c)\in E$. But $(a,b)\in E$. So $(a,c)\in E$ since $E$ is transitive. Therefore $c\in[a]$, which implies $[b]\subseteq[a]$. Collect all the information we have so far, this implies $[a]=[b]$. Therefore $P=\{[a]\mid a\in S\}$ forms a partitition of $S$ ($P$ is being interpreted as a set, not a multiset). In fact, $E=\bigcup\{[a]\times[a]\mid a\in S\}$. ∎

From the above proof, we also have

Corollary 1.

For every partition $P=\{P_{i}\mid i\in I\}$ of $S$, $E=\bigcup\{P_{i}^{2}\mid i\in I\}$ is an equivalence relation. Conversely, every equivalence relation on $S$ can be formed this way.

Title partition is equivalent to an equivalence relation PartitionIsEquivalentToAnEquivalenceRelation 2013-03-22 16:44:55 2013-03-22 16:44:55 CWoo (3771) CWoo (3771) 7 CWoo (3771) Derivation msc 03-00