Fundamental Theorem on Equivalence Relations

From ProofWiki
Jump to navigation Jump to search


Theorem

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


Then the quotient $S / \mathcal R$ of $S$ by $\mathcal R$ forms a partition of $S$.


Proof

To prove that $S / \mathcal R$ is a partition of $S$, we have to prove:

$(1): \quad \displaystyle \bigcup {S / \mathcal R} = S$
$(2): \quad \eqclass x {\mathcal R} \ne \eqclass y {\mathcal R} \iff \eqclass x {\mathcal R} \cap \eqclass y {\mathcal R} = \O$
$(3): \quad \forall \eqclass x {\mathcal R} \in S / \mathcal R: \eqclass x {\mathcal R} \ne \O$


Taking each proposition in turn:


Union of Equivalence Classes is Whole Set

The set of $\mathcal R$-classes constitutes the whole of $S$:

\(\displaystyle \) \(\) \(\displaystyle \forall x \in S: x \in \eqclass x {\mathcal R}\) Definition of Equivalence Class
\(\displaystyle \) \(\leadsto\) \(\displaystyle \neg \paren {\exists x \in S: x \notin \eqclass x {\mathcal R} }\) Assertion of Universality
\(\displaystyle \) \(\leadsto\) \(\displaystyle \neg \paren {\exists x \in S: x \notin \bigcup \eqclass x {\mathcal R} }\) Definition of Set Union
\(\displaystyle \) \(\leadsto\) \(\displaystyle \forall x \in S: x \in \bigcup S / \mathcal R\) Assertion of Universality
\(\displaystyle \) \(\leadsto\) \(\displaystyle S \subseteq \bigcup S / \mathcal R\) Definition of Subset


Also:

\(\displaystyle \) \(\) \(\displaystyle \forall X \in S / \mathcal R: X \subseteq S\) Definition of Equivalence Class
\(\displaystyle \) \(\leadsto\) \(\displaystyle \bigcup S / \mathcal R \subseteq S\) Union is Smallest Superset: General Result


By definition of set equality:

$\displaystyle \bigcup {S / \mathcal R} = S$

and so the set of $\mathcal R$-classes constitutes the whole of $S$.


$\Box$


Equivalence Classes are Disjoint

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.

$\Box$


Equivalence Class is not Empty

\(\, \displaystyle \forall \eqclass x {\mathcal R} \subseteq S: \exists x \in S: \, \) \(\displaystyle x\) \(\in\) \(\displaystyle \eqclass x {\mathcal R}\) Definition of Equivalence Class
\(\displaystyle \leadsto \ \ \) \(\displaystyle \eqclass x {\mathcal R}\) \(\ne\) \(\displaystyle \O\) Definition of Empty Set


$\Box$


Thus all conditions for $S / \mathcal R$ to be a partition are fulfilled.

$\blacksquare$


Examples

Arbitrary Equivalence on Set of $6$ Elements: $1$

Let $S = \set {1, 2, 3, 4, 5, 6}$.


Let $\mathcal R \subset S \times S$ be a relation on $S$ defined as:

$\mathcal R = \set {\tuple {1, 1}, \tuple {1, 2}, \tuple {1, 3}, \tuple {2, 1}, \tuple {2, 2}, \tuple {2, 3}, \tuple {3, 1}, \tuple {3, 2}, \tuple {3, 3}, \tuple {4, 4}, \tuple {4, 5}, \tuple {5, 4}, \tuple {5, 5}, \tuple {6, 6} }$


Then $\mathcal R$ is an equivalence relation which partitions $S$ into:

\(\displaystyle \eqclass 1 {\mathcal R}\) \(=\) \(\displaystyle \set {1, 2, 3}\)
\(\displaystyle \eqclass 4 {\mathcal R}\) \(=\) \(\displaystyle \set {4, 5}\)
\(\displaystyle \eqclass 6 {\mathcal R}\) \(=\) \(\displaystyle \set 6\)


Arbitrary Equivalence on Set of $6$ Elements: $2$

Let $S = \set {1, 2, 3, 4, 5, 6}$.


Let $\mathcal R \subset S \times S$ be an equivalence relation on $S$ with the properties:

\(\displaystyle 1\) \(\mathcal R\) \(\displaystyle 3\)
\(\displaystyle 3\) \(\mathcal R\) \(\displaystyle 4\)
\(\displaystyle 2\) \(\mathcal R\) \(\displaystyle 6\)
\(\displaystyle \forall a \in A: \ \ \) \(\displaystyle \size {\eqclass a {\mathcal R} }\) \(=\) \(\displaystyle 3\)


Then the equivalence classes of $\mathcal R$ are:

\(\displaystyle \eqclass 1 {\mathcal R}\) \(=\) \(\displaystyle \set {1, 3, 4}\)
\(\displaystyle \eqclass 2 {\mathcal R}\) \(=\) \(\displaystyle \set {2, 5, 6}\)


Also see


Sources