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

We have that:

\(\, \ds \forall x \in S: \, \) \(\ds x\) \(\in\) \(\ds \eqclass x \RR\) Definition of Equivalence Class
\(\text {(1)}: \quad\) \(\ds \leadsto \ \ \) \(\ds x\) \(\in\) \(\ds \set {y \in S: x \mathrel \RR y}\) Definition of Equivalence Class


and:

\(\ds \eqclass x \RR\) \(=\) \(\ds \set {y: x \mathrel \RR y}\) Definition of Equivalence Class
\(\text {(2)}: \quad\) \(\ds \) \(\subseteq\) \(\ds S\) Definition of Subset


Then:

\(\ds S\) \(=\) \(\ds \bigcup_{x \mathop \in S} \set x\) Definition of Union of Set of Sets
\(\ds \) \(\subseteq\) \(\ds \bigcup_{x \mathop \in S} \eqclass x \RR\) from $(1)$
\(\ds \) \(\subseteq\) \(\ds \bigcup_{x \mathop \in S} S\) from $(2)$
\(\ds \) \(=\) \(\ds S\)

$\blacksquare$


Also see


Sources