Union of Equivalence Classes is Whole Set

From ProofWiki
Jump to navigation Jump to search

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$


Also see


Sources