Union of Equivalence Classes is Whole Set

From ProofWiki
Jump to navigation Jump to search

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$


Also see


Sources