Equivalence Class holds Equivalent Elements

Theorem

Let $\mathcal R$ be an equivalence relation on a set $S$. Then:

$\left({x, y}\right) \in \mathcal R \iff \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R$

Proof

• First we prove that $\left({x, y}\right) \in \mathcal R \implies \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R$.

Suppose $\left({x, y}\right) \in \mathcal R: x, y \in S$.

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle z\)	\(\in\)	\(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({x, z}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Equivalence Class
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({z, x}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Equivalence Relation: $\mathcal R$ is symmetric
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({z, y}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Equivalence Relation: $\mathcal R$ is transitive
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({y, z}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Equivalence Relation: $\mathcal R$ is symmetric
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle z\)	\(\in\)	\(\displaystyle \left[\!\left[{y}\right]\!\right]_\mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Equivalence Class

So $\left[\!\left[{x}\right]\!\right]_\mathcal R \subseteq \left[\!\left[{y}\right]\!\right]_\mathcal R$.

Now:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\implies\)	\(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R \subseteq \left[\!\left[{y}\right]\!\right]_\mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	(see above)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\implies\)	\(\displaystyle \left({y, x}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Equivalence Relation: $\mathcal R$ is symmetric
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left[\!\left[{y}\right]\!\right]_\mathcal R \subseteq \left[\!\left[{x}\right]\!\right]_\mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	from above
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left[\!\left[{y}\right]\!\right]_\mathcal R = \left[\!\left[{x}\right]\!\right]_\mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Set Equality

... so we have shown that $\left({x, y}\right) \in \mathcal R \implies \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R$.

• Next we prove that $\left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R \implies \left({x, y}\right) \in \mathcal R$:

By definition of set equality, $\left[\!\left[{x}\right]\!\right]_{\mathcal R} = \left[\!\left[{y}\right]\!\right]_\mathcal R$ means $\left({x \in \left[\!\left[{x}\right]\!\right]_\mathcal R \iff x \in \left[\!\left[{y}\right]\!\right]_\mathcal R}\right)$.

So by definition of equivalence class$\left({y, x}\right) \in \mathcal R$.

Hence by definition of equivalence relation: $\mathcal R$ is symmetric, $\left({x, y}\right) \in \mathcal R$.

So we have shown that $\left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R \implies \left({x, y}\right) \in \mathcal R$.

• Thus, we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\implies\)	\(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R\)	\(\implies\)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

So by Material Equivalence, $\left({x, y}\right) \in \mathcal R \iff \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R$.

$\blacksquare$

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.4$: Lemma $\text{(i)}$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 17$
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 6$: Theorem $6.3 \ (2)$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 17.2, \ \S 17.3$