# Relation Induced by Partition is Equivalence

Jump to navigation Jump to search

## Theorem

Let $\mathbb S$ be a partition of a set $S$.

Let $\RR$ be the relation induced by $\mathbb S$.

Then:

$(1): \quad \RR$ is unique
$(2): \quad \RR$ is an equivalence relation on $S$.

Hence $\mathbb S$ is the quotient set of $S$ by $\RR$, that is:

$\mathbb S = S / \RR$

## Proof

Let $\mathbb S$ be a partition of $S$.

From Relation Induced by Partition, we define the relation $\RR$ on $S$ by:

$\RR = \set {\tuple {x, y}: \paren {\exists T \in \mathbb S: x \in T \land y \in T} }$

### Test for Equivalence

We are to show that $\RR$ is an equivalence relation.

Checking in turn each of the critera for equivalence:

#### Reflexive

$\RR$ is reflexive:

 $\ds$  $\ds \paren {x \in T \land x \in T}$ Rule of Idempotence $\ds$ $\leadstoandfrom$ $\ds \tuple {x, x} \in \RR$ Definition of $\RR$

$\Box$

#### Symmetric

$\RR$ is symmetric:

 $\ds$  $\ds \tuple {x, y} \in \RR$ $\ds$ $\leadsto$ $\ds x \in T \land y \in T$ Definition of $\RR$ $\ds$ $\leadsto$ $\ds y \in T \land x \in T$ Rule of Commutation $\ds$ $\leadsto$ $\ds \tuple {y, x} \in \RR$ Definition of $\RR$

$\Box$

#### Transitive

$\RR$ is transitive:

 $\ds x \in T \land y \in T$ $\leadstoandfrom$ $\ds \tuple {x, y} \in \RR$ Definition of $\RR$ $\ds y \in T \land z \in T$ $\leadstoandfrom$ $\ds \tuple {y, z} \in \RR$ Definition of $\RR$ $\ds \paren {x \in T \land y \in T} \land \paren {y \in T \land z \in T}$ $\leadstoandfrom$ $\ds \tuple {x, z} \in \RR$ Definition of $\RR$

$\Box$

So $\RR$ is reflexive, symmetric and transitive.

Hence, by definition, $\RR$ is an equivalence relation.

$\Box$

### Test for Uniqueness

Now by definition of a partition, we have that:

$\mathbb S$ partitions $S \implies \forall x \in S: \exists T \in \mathbb S: x \in T$

Also:

 $\ds x, y \in T$ $\leadsto$ $\ds \tuple {x, y} \in \RR$ Definition of $\RR$ $\ds x \in T_1, y \in T_2, T_1 \ne T_2$ $\leadsto$ $\ds \tuple{x, y} \notin \RR$ Definition of Set Partition

Thus $\mathbb S$ is the set of $\RR$-classes constructed above, and no other relation can be constructed in this way.

$\blacksquare$