# Fundamental Theorem on Equivalence Relations

## Theorem

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

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

## Proof

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

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

Taking each proposition in turn:

### Union of Equivalence Classes is Whole Set

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

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

Also:

 $\displaystyle$  $\displaystyle \forall X \in S / \RR: X \subseteq S$ Definition of Equivalence Class $\displaystyle$ $\leadsto$ $\displaystyle \bigcup S / \RR \subseteq S$ Union is Smallest Superset: General Result

By definition of set equality:

$\displaystyle \bigcup S / \RR = S$

and so the set of $\RR$-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 / \RR$ 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 $\RR \subset S \times S$ be an equivalence relation on $S$ with the properties:

 $\displaystyle 1$ $\RR$ $\displaystyle 3$ $\displaystyle 3$ $\RR$ $\displaystyle 4$ $\displaystyle 2$ $\RR$ $\displaystyle 6$ $\displaystyle \forall a \in A: \ \$ $\displaystyle \size {\eqclass a \RR}$ $=$ $\displaystyle 3$

Then the equivalence classes of $\RR$ are:

 $\displaystyle \eqclass 1 \RR$ $=$ $\displaystyle \set {1, 3, 4}$ $\displaystyle \eqclass 2 \RR$ $=$ $\displaystyle \set {2, 5, 6}$