partition is equivalent to an equivalence relation

Proposition 1.

There is a one-to-one correspondence between the set $\mathrm{Part}\mathit{}\mathrm{(}S\mathrm{)}$ of partitions of $S$ and the set $\mathrm{Equiv}\mathit{}\mathrm{(}S\mathrm{)}$ 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\mathrm{=}\mathrm{\{}{P}_i\mathrm{\mid }i\mathrm{\in }I\mathrm{\}}$ of $S$, $E\mathrm{=}\mathrm{\bigcup }\mathrm{\{}{P}_i^{\mathrm{2}}\mathrm{\mid }i\mathrm{\in }I\mathrm{\}}$ is an equivalence relation. Conversely, every equivalence relation on $S$ can be formed this way.

Title	partition is equivalent to an equivalence relation
Canonical name	PartitionIsEquivalentToAnEquivalenceRelation
Date of creation	2013-03-22 16:44:55
Last modified on	2013-03-22 16:44:55
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 03-00