Equivalence Class Equivalent Statements
Theorem
Let $\RR$ be an equivalence relation on $S$.
Let $x, y \in S$.
The following statements are equivalent:
- $(1): \quad x$ and $y$ are in the same $\RR$-class
- $(2): \quad \eqclass x \RR = \eqclass y \RR$
- $(3): \quad x \mathrel \RR y$
- $(4): \quad x \in \eqclass y \RR$
- $(5): \quad y \in \eqclass x \RR$
- $(6): \quad \eqclass x \RR \cap \eqclass y \RR \ne \O$
Proof
$(1)$ Equivalent to $(2)$
By Equivalence Class is Unique:
- $\eqclass x \RR$ is the unique $\RR$-class to which $x$ belongs
and:
- $\eqclass y \RR$ is the unique $\RR$-class to which $y$ belongs.
As these are unique for each, they must be the same set.
$\blacksquare$
$(2)$ Equivalent to $(3)$
By Equivalence Class holds Equivalent Elements:
Necessary Condition
First we prove that $\tuple {x, y} \in \RR \implies \eqclass x \RR = \eqclass y \RR$.
Suppose:
- $\tuple {x, y} \in \RR: x, y \in S$
Then:
\(\ds z\) | \(\in\) | \(\ds \eqclass x \RR\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {x, z}\) | \(\in\) | \(\ds \RR\) | Definition of Equivalence Class | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {z, x}\) | \(\in\) | \(\ds \RR\) | Definition of Equivalence Relation: $\RR$ is symmetric | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {z, y}\) | \(\in\) | \(\ds \RR\) | Definition of Equivalence Relation: $\RR$ is transitive | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {y, z}\) | \(\in\) | \(\ds \RR\) | Definition of Equivalence Relation: $\RR$ is symmetric | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds z\) | \(\in\) | \(\ds \eqclass y \RR\) | Definition of Equivalence Class |
So:
- $\eqclass x \RR \subseteq \eqclass y \RR$
Now:
\(\ds \tuple {x, y} \in \RR\) | \(\implies\) | \(\ds \eqclass x \RR \subseteq \eqclass y \RR\) | (see above) | |||||||||||
\(\ds \tuple {x, y} \in \RR\) | \(\implies\) | \(\ds \tuple {y, x} \in \RR\) | Definition of Equivalence Relation: $\RR$ is symmetric | |||||||||||
\(\ds \) | \(\leadsto\) | \(\ds \eqclass y \RR \subseteq \eqclass x \RR\) | from above | |||||||||||
\(\ds \) | \(\leadsto\) | \(\ds \eqclass y \RR = \eqclass x \RR\) | Definition of Set Equality |
... so we have shown that:
- $\tuple {x, y} \in \RR \implies \eqclass x \RR = \eqclass y \RR$
$\Box$
Sufficient Condition
Next we prove that $\eqclass x \RR = \eqclass y \RR \implies \tuple {x, y} \in \RR$.
By definition of set equality:
- $\eqclass x \RR = \eqclass y \RR$
means:
- $\paren {x \in \eqclass x \RR \iff x \in \eqclass y \RR}$
So by definition of equivalence class:
- $\tuple {y, x} \in \RR$
Hence by definition of equivalence relation: $\RR$ is symmetric
- $\tuple {x, y} \in \RR$
So we have shown that
- $\eqclass x \RR = \eqclass y \RR \implies \tuple {x, y} \in \RR$
Thus, we have:
\(\ds \tuple {x, y} \in \RR\) | \(\implies\) | \(\ds \eqclass x \RR = \eqclass y \RR\) | ||||||||||||
\(\ds \eqclass x \RR = \eqclass y \RR\) | \(\implies\) | \(\ds \tuple {x, y} \in \RR\) |
$\Box$
So by equivalence:
- $\tuple {x, y} \in \RR \iff \eqclass x \RR = \eqclass y \RR$
$\blacksquare$
$(3)$ Equivalent to $(4)$
This follows directly by the definition of equivalence class.
$\blacksquare$
$(3)$ Equivalent to $(5)$
This follows through dint of the symmetry of $\RR$ and the definition of Equivalence Class.
$\blacksquare$
$(3)$ Equivalent to $(6)$
Follows directly from Equivalence Classes are Disjoint.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 10$: Equivalence Relations: Theorem $10.4$