Equivalence Classes are Disjoint/Proof 2

From ProofWiki
Jump to: navigation, 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$:

$\left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R \ne \varnothing$

Let:

$z \in \left[\!\left[{x}\right]\!\right]_\mathcal R$
$z \in \left[\!\left[{y}\right]\!\right]_\mathcal R$

Then by definition of equivalence class:

$\left({x, z}\right) \in \mathcal R$
$\left({y, z}\right) \in \mathcal R$


Let $c \in \left[\!\left[{x}\right]\!\right]_\mathcal R$.

That is:

$\left({x, c}\right) \in \mathcal R$

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

$\left({z, x}\right) \in \mathcal R$

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

$\left({z, x}\right) \in \mathcal R \land \left({x, c}\right) \in \mathcal R \implies \left({z, c}\right) \in \mathcal R$

and

$\left({y, z}\right) \in \mathcal R \land \left({z, c}\right) \in \mathcal R \implies \left({y, c}\right) \in \mathcal R$

So we have $c \in \left[\!\left[{y}\right]\!\right]_\mathcal R$.

By definition of subset:

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


Similarly, let $c \in \left[\!\left[{y}\right]\!\right]_\mathcal R$.

That is:

$\left({y, c}\right) \in \mathcal R$

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

$\left({z, y}\right) \in \mathcal R$

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

$\left({z, y}\right) \in \mathcal R \land \left({y, c}\right) \in \mathcal R \implies \left({z, c}\right) \in \mathcal R$

and

$\left({x, z}\right) \in \mathcal R \land \left({z, c}\right) \in \mathcal R \implies \left({x, c}\right) \in \mathcal R$

So we have $c \in \left[\!\left[{x}\right]\!\right]_\mathcal R$.

By definition of subset:

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


That is:

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

and

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

By definition of set equality:

$\left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R$


Thus: $\left[\!\left[{x}\right]\!\right]_\mathcal R \cap \left[\!\left[{y}\right]\!\right]_\mathcal R \ne \varnothing \implies \left[\!\left[{x}\right]\!\right]_\mathcal R = \left[\!\left[{y}\right]\!\right]_\mathcal R$

and the result follows.

$\blacksquare$


Sources