Relation Induced by Quotient Set is Equivalence

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal R$ be an equivalence relation on $S$.

Let $S / \mathcal R$ be the quotient set of $S$ determined by $\mathcal R$.

Let $\mathcal R'$ be the relation induced by $S / \mathcal R$ on $S$.


Then $\mathcal R' = \mathcal R$.


Proof

Let $\mathcal R$ be an equivalence relation on $S$.

Let $\left({x, y}\right) \in \mathcal R$.

By definition of equivalence class, $y \in \left[\!\left[{x}\right]\!\right]_\mathcal R$ and $x \in \left[\!\left[{x}\right]\!\right]_\mathcal R$.

By definition of quotient set, $x$ and $y$ both belong to the same element of $S / \mathcal R$.

So, by definition of $\mathcal R'$, it follows that $\left({x, y}\right) \in \mathcal R'$.

That is:

$\left({x, y}\right) \in \mathcal R \implies \left({x, y}\right) \in \mathcal R'$

and so by definition of subset:

$\mathcal R \subseteq \mathcal R'$


Now let $\left({x, y}\right) \in \mathcal R'$.

Then $y$ belongs to the same element of $S / \mathcal R$ that $x$ does.

That is:

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

and so $\left({x, y}\right) \in \mathcal R$.

That is:

$\left({x, y}\right) \in \mathcal R' \implies \left({x, y}\right) \in \mathcal R$

and so by definition of subset:

$\mathcal R' \subseteq \mathcal R$


The result follows by definition of set equality.

$\blacksquare$


Sources