Theorem 0.22

Return to Theorems, Glossary, Homework Problems.


(Equivalence Relations and Partitions) Let $S$ be a nonempty set and let $\sim$ be an equivalence relation on $S$. Then $\sim$ yields a partition of $S$, where

\begin{align} \bar{a}=\{x\in S \ | \ x\sim a\}. \end{align}

Also, each partition of $S$ gives rise to an equivalence relation $\sim$ on $S$ where $a\sim b$ if and only if $a$ and $b$ are in the same cell of the partition.


We must show that the different cells $\bar{a} =\{x \in S \ | \ x\sim a\}$ for $a \in S$ do give a partition of $S$, so that every element of $S$ is in some cell and so that if $a \in \bar{b}$, then $\bar{a} = \bar{b}$. Let $a \in S$. Then $a \in \bar{a}$ by the reflexive condition (1), so $a$ is in at least one cell.

Suppose now that $a$ were in a cell $\bar{b}$ also. We need to show that $\bar{a} = \bar{b}$ as sets; this will show that $a$ cannot be in more than one cell. There is a standard way to show that two sets are the same:

Show that each set is a subset of the other.

We show that $\bar{a} \subseteq \bar{b}$. Let $x \in \bar{a}$. Then $x \sim a$. But $a \in \bar{b}$, so $a \sim b$. Then, by the transitive condition (3), $x \sim b$, so $x \in \bar{b}$. Thus $\bar{a} \subseteq \bar{b}$. Now we show that $\bar{b} \subseteq \bar{a}$. Let $y \in \bar{b}$. Then $y \sim b$. But $a \in \bar{b}$ and, by symmetry (2), $b \sim a$. Then by transitivity (3), $y\sim a$, so $y \in \bar{a}$. Hence $\bar{b} \subseteq \bar{a}$ also, so $\bar{b} = \bar{a}$ and our proof is complete.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License