Equivalence Classes are Disjoint/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then all $\RR$-classes are pairwise disjoint:

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


Proof

First we show that:

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


Suppose two $\RR$-classes are not disjoint:

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


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


Therefore, by the Rule of Transposition:

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


Now we show that:

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


Suppose $\tuple {x, y} \in \RR$.

\(\ds \) \(\) \(\ds y \in \eqclass y \RR\) Definition of Equivalence Class
\(\ds \) \(\) \(\ds \tuple {x, y} \in \RR\) by hypothesis
\(\ds \) \(\leadsto\) \(\ds y \in \eqclass x \RR\) Definition of Equivalence Class
\(\ds \) \(\leadsto\) \(\ds y \in \eqclass x \RR \land y \in \eqclass y \RR\) Rule of Conjunction
\(\ds \) \(\leadsto\) \(\ds y \in \eqclass x \RR \cap \eqclass y \RR\) Definition of Set Intersection
\(\ds \) \(\leadsto\) \(\ds \eqclass x \RR \cap \eqclass y \RR \ne \O\) Definition of Empty Set


Thus we have shown that:

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


Therefore, by the Rule of Transposition:

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


Using the rule of Biconditional Introduction on these results:

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

and the proof is complete.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_Classes_are_Disjoint/Proof_1&oldid=501156"