Equivalence Classes are Disjoint/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then all $\mathcal R$-classes are pairwise disjoint:

$\tuple {x, y} \notin \mathcal R \iff \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} = \O$


Proof

Suppose that for $x, y \in S$:

$\eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O$

Let:

$z \in \eqclass x {\mathcal R}$
$z \in \eqclass y {\mathcal R}$

Then by definition of equivalence class:

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


Let $c \in \eqclass x {\mathcal R}$.

That is:

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

By definition of equivalence relation, $\mathcal R$ is symmetric so:

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

By definition of equivalence relation, $\mathcal R$ is transitive so:

$\tuple {z, x} \in \mathcal R \land \tuple {x, c} \in \mathcal R \implies \tuple {z, c} \in \mathcal R$

and

$\tuple {y, z} \in \mathcal R \land \tuple {z, c} \in \mathcal R \implies \tuple {y, c} \in \mathcal R$

So we have $c \in \eqclass y {\mathcal R}$.

By definition of subset:

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


Similarly, let $c \in \eqclass y {\mathcal R}$.

That is:

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

By definition of equivalence relation, $\mathcal R$ is symmetric so:

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

By definition of equivalence relation, $\mathcal R$ is transitive so:

$\tuple {z, y} \in \mathcal R \land \tuple {y, c} \in \mathcal R \implies \tuple {z, c} \in \mathcal R$

and

$\tuple {x, z} \in \mathcal R \land \tuple {z, c} \in \mathcal R \implies \tuple {x, c} \in \mathcal R$

So we have $c \in \eqclass x {\mathcal R}$.

By definition of subset:

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


That is:

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

and

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

By definition of set equality:

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


Thus:

$\eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O \implies \eqclass x {\mathcal R} = \eqclass y {\mathcal R}$

and the result follows.

$\blacksquare$


Sources