Union of Equivalence Classes is Whole Set
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
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.3$: Equivalence Relations: Theorem $\text{A}.2$
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): $\S 17.5 \ \text{(i)}$: Equivalence classes
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: Exercises: $1.8$
- 2000: James R. Munkres: Topology (2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 3$: Relations
- Greg Martin (https://math.stackexchange.com/users/16078/greg-martin), Prove union of equivalence classes is the whole set, URL (version: 2020-01-30): https://math.stackexchange.com/q/3527923