# Quotient Set Determined by Relation Induced by Partition is That Partition

Jump to navigation
Jump to search

## Theorem

Let $S$ be a set.

Let $\mathcal P$ be a partition of $S$.

Let $\mathcal R$ be the relation induced by $\mathcal P$.

Then the quotient set $S / \mathcal R$ of $S$ is $\mathcal P$ itself.

## Proof

Let $P \subseteq S$ such that $P \in \mathcal P$.

Let $x \in P$.

Then:

\(\displaystyle y\) | \(\in\) | \(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R\) | |||||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle \left({x, y}\right)\) | \(\in\) | \(\displaystyle \mathcal R\) | by definition of equivalence class | |||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle y\) | \(\in\) | \(\displaystyle P\) | by definition of relation induced by $\mathcal P$ |

Therefore:

- $P = \left[\!\left[{x}\right]\!\right]_\mathcal R$

and so:

- $P \in S / \mathcal R$

and so:

- $\mathcal P \subseteq S / \mathcal R$

Now let $x \in S$.

As $\mathcal P$ is a partition:

- $\exists P \in \mathcal P: x \in P$

Then by definition of $\mathcal R$:

- $\left({x, y}\right) \in \mathcal R \iff y \in \left[\!\left[{x}\right]\!\right]_\mathcal R$

\(\displaystyle y\) | \(\in\) | \(\displaystyle P\) | |||||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle \left({x, y}\right)\) | \(\in\) | \(\displaystyle \mathcal R\) | by definition of relation induced by $\mathcal P$ | |||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle y\) | \(\in\) | \(\displaystyle \left[\!\left[{x}\right]\!\right]_\mathcal R\) | by definition of equivalence class |

Therefore:

- $\left[\!\left[{x}\right]\!\right]_\mathcal R = P$

and so:

- $\left[\!\left[{x}\right]\!\right]_\mathcal R \in \mathcal P$

That is:

- $\mathcal S / \mathcal R \subseteq P$

It follows by definition of set equality that:

- $\mathcal S / \mathcal R = P$

Hence the result.

$\blacksquare$

## Sources

- 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): $\S 10$: Theorem $10.3$