# Union of Equivalence Classes is Whole Set

Jump to navigation
Jump to search

## Contents

## 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

- 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 - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 3$: Relations