Equivalence Classes are Disjoint/Proof 1

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

First we show that:

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


Suppose two $\mathcal R$-classes are not disjoint:

\(\displaystyle \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O\) \(\leadsto\) \(\displaystyle \exists z: z \in \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R}\) $\quad$ Definition of Empty Set $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists z: z \in \eqclass x {\mathcal R} \land z \in \eqclass y {\mathcal R}\) $\quad$ Definition of Set Intersection $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists z: \paren {\tuple {x, z} \in \mathcal R} \land \paren {\tuple {y, z} \in \mathcal R}\) $\quad$ Definition of Equivalence Class $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists z: \paren {\tuple {x, z} \in \mathcal R} \land \paren {\tuple {x, y} \in \mathcal R}\) $\quad$ Definition of Symmetric Relation: $\mathcal R$ is symmetric $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \tuple {x, y} \in \mathcal R\) $\quad$ Definition of Transitive Relation: $\mathcal R$ is transitive $\quad$


Thus we have shown that $\eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O \implies \tuple {x, y} \in \mathcal R$.


Therefore, by the Rule of Transposition:

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


Now we show that:

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


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

\(\displaystyle \) \(\) \(\displaystyle y \in \eqclass y {\mathcal R}\) $\quad$ Definition of Equivalence Class $\quad$
\(\displaystyle \) \(\) \(\displaystyle \tuple {x, y} \in \mathcal R\) $\quad$ by hypothesis $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle y \in \eqclass x {\mathcal R}\) $\quad$ Definition of Equivalence Class $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle y \in \eqclass x {\mathcal R} \land y \in \eqclass y {\mathcal R}\) $\quad$ Rule of Conjunction $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle y \in \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R}\) $\quad$ Definition of Set Intersection $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O\) $\quad$ Definition of Empty Set $\quad$


Thus we have shown that:

$\tuple {x, y} \in \mathcal R \implies \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O$


Therefore, by the Rule of Transposition:

$\eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} = \O \implies \paren {x, y} \notin \mathcal R$


Using the rule of Biconditional Introduction on these results:

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

and the proof is finished.

$\blacksquare$


Sources