# Equivalence Classes are Disjoint

## 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 1

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}$ Definition of Empty Set $\displaystyle$ $\leadsto$ $\displaystyle \exists z: z \in \eqclass x {\mathcal R} \land z \in \eqclass y {\mathcal R}$ Definition of Set Intersection $\displaystyle$ $\leadsto$ $\displaystyle \exists z: \paren {\tuple {x, z} \in \mathcal R} \land \paren {\tuple {y, z} \in \mathcal R}$ Definition of Equivalence Class $\displaystyle$ $\leadsto$ $\displaystyle \exists z: \paren {\tuple {x, z} \in \mathcal R} \land \paren {\tuple {x, y} \in \mathcal R}$ Definition of Symmetric Relation: $\mathcal R$ is symmetric $\displaystyle$ $\leadsto$ $\displaystyle \tuple {x, y} \in \mathcal R$ Definition of Transitive Relation: $\mathcal R$ is transitive

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}$ Definition of Equivalence Class $\displaystyle$  $\displaystyle \tuple {x, y} \in \mathcal R$ by hypothesis $\displaystyle$ $\leadsto$ $\displaystyle y \in \eqclass x {\mathcal R}$ Definition of Equivalence Class $\displaystyle$ $\leadsto$ $\displaystyle y \in \eqclass x {\mathcal R} \land y \in \eqclass y {\mathcal R}$ Rule of Conjunction $\displaystyle$ $\leadsto$ $\displaystyle y \in \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R}$ Definition of Set Intersection $\displaystyle$ $\leadsto$ $\displaystyle \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} \ne \O$ Definition of Empty Set

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$

## Proof 2

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

$\eqclass x {\RR} \cap \eqclass y \RR \ne \O$

Let:

$z \in \eqclass x \RR$
$z \in \eqclass y \RR$

Then by definition of equivalence class:

$\tuple {x, z} \in \RR$
$\tuple {y, z} \in \RR$

Let $c \in \eqclass x \RR$.

That is:

$\tuple {x, c} \in \RR$

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

$\tuple {z, x} \in \RR$

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

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

and

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

So we have $c \in \eqclass y \RR$.

By definition of subset:

$\eqclass x \RR \subseteq \eqclass y \RR$

Similarly, let $c \in \eqclass y \RR$.

That is:

$\tuple {y, c} \in \RR$

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

$\tuple {z, y} \in \RR$

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

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

and

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

So we have $c \in \eqclass x \RR$.

By definition of subset:

$\eqclass y \RR \subseteq \eqclass x \RR$

That is:

$\eqclass x \RR \subseteq \eqclass y \RR$

and

$\eqclass y \RR \subseteq \eqclass x \RR$

By definition of set equality:

$\eqclass x \RR = \eqclass y \RR$

Thus:

$\eqclass x \RR \cap \eqclass y \RR \ne \O \implies \eqclass x \RR = \eqclass y \RR$

and the result follows.

$\blacksquare$