# 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 |