Fundamental Theorem on Equivalence Relations
From ProofWiki
Contents |
Theorem
Let $\mathcal R \subseteq S \times S$ be an equivalence on a set $S$.
Then the quotient $S / \mathcal R$ of $S$ by $\mathcal R$ forms a partition of $S$.
Proof
To prove that $S / \mathcal R$ is a partition of $S$, we have to prove:
- $(1): \quad \displaystyle \bigcup {S / \mathcal R} = S$
- $(2): \quad \left[\!\left[{x}\right]\!\right]_\mathcal R \ne \left[\!\left[{y}\right]\!\right]_\mathcal R \iff \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R = \varnothing$
- $(3): \quad \forall \left[\!\left[{x}\right]\!\right]_\mathcal R \in S / \mathcal R: \left[\!\left[{x}\right]\!\right]_\mathcal R \ne \varnothing$
Taking each proposition in turn:
Union of Equivalence Classes is Whole Set
The set of $\mathcal R$-classes constitutes the whole of $S$:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \forall x \in S: x \in \left[\!\left[{x}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \neg \left({\exists x \in S: x \notin \left[\!\left[{x}\right]\!\right]_\mathcal R}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws (Predicate Logic) | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \neg \left({\exists x \in S: x \notin \bigcup \left[\!\left[{x}\right]\!\right]_\mathcal R}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Union | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \forall x \in S: x \in \bigcup S / \mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | De Morgan's Laws (Predicate Logic) | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle S \subseteq \bigcup S / \mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Subset |
Also:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \forall x \in S: \left[\!\left[{x}\right]\!\right]_\mathcal R \subseteq S\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Equivalence Class | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \bigcup \left[\!\left[{x}\right]\!\right]_\mathcal R \subseteq S\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Union Smallest: General Result | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \bigcup S / \mathcal R \subseteq S\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Quotient Set |
From Equality of Sets, $\displaystyle \bigcup {S / \mathcal R} = S$, and so the set of $\mathcal R$-classes constitutes the whole of $S$.
$\Box$
Equivalence Classes are Disjoint
- First we show that $\left({x, y}\right) \notin \mathcal R \implies \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R = \varnothing$:
Suppose two $\mathcal R$-classes are not disjoint:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R \ne \varnothing\) | \(\implies\) | \(\displaystyle \exists z: z \in \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of the Empty Set | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \exists z: z \in \left[\!\left[{x}\right]\!\right]_\mathcal R \land z \in \left[\!\left[{y}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Intersection | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \exists z: \left({\left({x, z}\right) \in \mathcal R}\right) \land \left({\left({y, z}\right) \in \mathcal R}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Equivalence Class | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \exists z: \left({\left({x, z}\right) \in \mathcal R}\right) \land \left({\left({z, y}\right) \in \mathcal R}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | $\mathcal R$ is symmetric | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \left({x, y}\right) \in \mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | $\mathcal R$ is transitive |
Thus we have shown that $\left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R \ne \varnothing \implies \left({x, y}\right) \in \mathcal R$.
Therefore, by the Rule of Transposition:
- $\left({x, y}\right) \notin \mathcal R \implies \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R = \varnothing$
- Now we show that $\left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R = \varnothing \implies \left({x, y}\right) \notin \mathcal R$:
Suppose $\left({x, y}\right) \in \mathcal R$.
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle y \in \left[\!\left[{y}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by definition | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \left({x, y}\right) \in \mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | by hypothesis | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle y \in \left[\!\left[{x}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Equivalence Class | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle y \in \left[\!\left[{x}\right]\!\right]_\mathcal R \land y \in \left[\!\left[{y}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Rule of Conjunction | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle y \in \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Intersection | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R \ne \varnothing\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Empty Set |
Thus we have shown that $\left({x, y}\right) \in \mathcal R \implies \left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R \ne \varnothing$.
Therefore, by the Rule of Transposition:
- $\left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R = \varnothing \implies \left({x, y}\right) \notin \mathcal R$
- Using the rule of Material Equivalence on these results:
- $\left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R = \varnothing \iff \left({x, y}\right) \notin \mathcal R$
... and the proof is finished.
$\Box$
Equivalence Class is Not Empty
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \forall \left[\!\left[{x}\right]\!\right]_\mathcal R \subseteq S: \exists x \in S: x\) | \(\in\) | \(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of Equivalence Class | ||
| \(\displaystyle \) | \(\displaystyle \implies\) | \(\displaystyle \) | \(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R\) | \(\ne\) | \(\displaystyle \varnothing\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Definition of the Empty Set |
$\Box$
Thus all conditions for $S / \mathcal R$ to be a partition are fulfilled.
$\blacksquare$
Also see
Sources
- Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 3$
- W.E. Deskins: Abstract Algebra (1964): $\S 1.2$: Theorem $1.10$
- J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.4$
- Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 10$: Theorem $10.1$
- Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.3$: Theorem $5$ Part $\text{I}$
- Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.3$: Theorem $\text{A}.2$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 17.5$
- Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.5$: Exercise $1.5.2$
- John F. Humphreys: A Course in Group Theory (1996): $\S 2$: Proposition $2.29$
