# Union of Equivalence Classes is Whole Set

## Theorem

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

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

## Proof

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

Also:

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

By definition of set equality:

$\displaystyle \bigcup S / \RR = S$

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

$\blacksquare$