Relation Induced by Partition is Equivalence

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathcal R$ be the relation induced by $\mathbb S$.


Then:

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

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

$\mathbb S = S / \mathcal R$


Proof

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

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

$\mathcal R = \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 $\mathcal R$ is an equivalence relation.

Checking in turn each of the critera for equivalence:


Reflexive

$\mathcal R$ is reflexive:

\(\displaystyle \) \(\) \(\displaystyle \paren {x \in T \land x \in T}\) Rule of Idempotence
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \tuple {x, x} \in \mathcal R\) Definition of $\mathcal R$

$\Box$


Symmetric

$\mathcal R$ is symmetric:

\(\displaystyle \) \(\) \(\displaystyle \tuple {x, y} \in \mathcal R\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle x \in T \land y \in T\) Definition of $\mathcal R$
\(\displaystyle \) \(\leadsto\) \(\displaystyle y \in T \land x \in T\) Rule of Commutation
\(\displaystyle \) \(\leadsto\) \(\displaystyle \tuple {y, x} \in \mathcal R\) Definition of $\mathcal R$

$\Box$


Transitive

$\mathcal R$ is transitive:

\(\displaystyle x \in T \land y \in T\) \(\leadstoandfrom\) \(\displaystyle \tuple {x, y} \in \mathcal R\) Definition of $\mathcal R$
\(\displaystyle y \in T \land z \in T\) \(\leadstoandfrom\) \(\displaystyle \tuple {y, z} \in \mathcal R\) Definition of $\mathcal R$
\(\displaystyle \paren {x \in T \land y \in T} \land \paren {y \in T \land z \in T}\) \(\leadstoandfrom\) \(\displaystyle \tuple {x, z} \in \mathcal R\) Definition of $\mathcal R$

$\Box$


So $\mathcal R$ is reflexive, symmetric and transitive, therefore $\mathcal R$ 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:

\(\displaystyle x, y \in T\) \(\leadsto\) \(\displaystyle \tuple {x, y} \in \mathcal R\) Definition of $\mathcal R$
\(\displaystyle x \in T_1, y \in T_2, T_1 \ne T_2\) \(\leadsto\) \(\displaystyle \tuple{x, y} \notin \mathcal R\) Definition of Set Partition


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

$\blacksquare$


Also see


Sources