# Union of Equivalence Classes is Whole Set

## Theorem

Let $\mathcal R \subseteq S \times S$ be an equivalence on a set $S$.

Then the set of $\mathcal R$-classes constitutes the whole of $S$.

## Proof

 $\displaystyle$  $\displaystyle \forall x \in S: x \in \eqclass x {\mathcal R}$ Definition of Equivalence Class $\displaystyle$ $\leadsto$ $\displaystyle \neg \paren {\exists x \in S: x \notin \eqclass x {\mathcal R} }$ Assertion of Universality $\displaystyle$ $\leadsto$ $\displaystyle \neg \paren {\exists x \in S: x \notin \bigcup \eqclass x {\mathcal R} }$ Definition of Set Union $\displaystyle$ $\leadsto$ $\displaystyle \forall x \in S: x \in \bigcup S / \mathcal R$ Assertion of Universality $\displaystyle$ $\leadsto$ $\displaystyle S \subseteq \bigcup S / \mathcal R$ Definition of Subset

Also:

 $\displaystyle$  $\displaystyle \forall X \in S / \mathcal R: X \subseteq S$ Definition of Equivalence Class $\displaystyle$ $\leadsto$ $\displaystyle \bigcup S / \mathcal R \subseteq S$ Union is Smallest Superset: General Result

By definition of set equality:

$\displaystyle \bigcup {S / \mathcal R} = S$

and so the set of $\mathcal R$-classes constitutes the whole of $S$.

$\blacksquare$