Equivalence Class holds Equivalent Elements

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then:

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


Proof

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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_Class_holds_Equivalent_Elements&oldid=522970"