Equivalence Class holds Equivalent Elements

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then:

$\tuple {x, y} \in \mathcal R \iff \eqclass x {\mathcal R} = \eqclass y {\mathcal R}$


Proof

Necessary Condition

First we prove that $\tuple {x, y} \in \mathcal R \implies \eqclass x {\mathcal R} = \eqclass y {\mathcal R}$.

Suppose:

$\tuple {x, y} \in \mathcal R: x, y \in S$

Then:

\(\displaystyle z\) \(\in\) \(\displaystyle \eqclass x {\mathcal R}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {x, z}\) \(\in\) \(\displaystyle \mathcal R\) Definition of Equivalence Class
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {z, x}\) \(\in\) \(\displaystyle \mathcal R\) Definition of Equivalence Relation: $\mathcal R$ is symmetric
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {z, y}\) \(\in\) \(\displaystyle \mathcal R\) Definition of Equivalence Relation: $\mathcal R$ is transitive
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {y, z}\) \(\in\) \(\displaystyle \mathcal R\) Definition of Equivalence Relation: $\mathcal R$ is symmetric
\(\displaystyle \leadsto \ \ \) \(\displaystyle z\) \(\in\) \(\displaystyle \eqclass y {\mathcal R}\) Definition of Equivalence Class

So:

$\eqclass x {\mathcal R} \subseteq \eqclass y {\mathcal R}$


Now:

\(\displaystyle \tuple {x, y} \in \mathcal R\) \(\implies\) \(\displaystyle \eqclass x {\mathcal R} \subseteq \eqclass y {\mathcal R}\) (see above)
\(\displaystyle \tuple {x, y} \in \mathcal R\) \(\implies\) \(\displaystyle \tuple {y, x} \in \mathcal R\) Definition of Equivalence Relation: $\mathcal R$ is symmetric
\(\displaystyle \) \(\leadsto\) \(\displaystyle \eqclass y {\mathcal R} \subseteq \eqclass x {\mathcal R}\) from above
\(\displaystyle \) \(\leadsto\) \(\displaystyle \eqclass y {\mathcal R} = \eqclass x {\mathcal R}\) Definition of Set Equality


... so we have shown that:

$\tuple {x, y} \in \mathcal R \implies \eqclass x {\mathcal R} = \eqclass y {\mathcal R}$.

$\Box$


Sufficient Condition

Next we prove that $\eqclass x {\mathcal R} = \eqclass y {\mathcal R} \implies \tuple {x, y} \in \mathcal R$.

By definition of set equality:

$\eqclass x {\mathcal R} = \eqclass y {\mathcal R}$

means:

$\paren {x \in \eqclass x {\mathcal R} \iff x \in \eqclass y {\mathcal R} }$

So by definition of equivalence class:

$\tuple {y, x} \in \mathcal R$

Hence by definition of equivalence relation: $\mathcal R$ is symmetric

$\tuple {x, y} \in \mathcal R$

So we have shown that

$\eqclass x {\mathcal R} = \eqclass y {\mathcal R} \implies \tuple {x, y} \in \mathcal R$


Thus, we have:

\(\displaystyle \tuple {x, y} \in \mathcal R\) \(\implies\) \(\displaystyle \eqclass x {\mathcal R} = \eqclass y {\mathcal R}\)
\(\displaystyle \eqclass x {\mathcal R} = \eqclass y {\mathcal R}\) \(\implies\) \(\displaystyle \tuple {x, y} \in \mathcal R\)

$\Box$


So by equivalence:

$\tuple {x, y} \in \mathcal R \iff \eqclass x {\mathcal R} = \eqclass y {\mathcal R}$

$\blacksquare$


Sources