Composite of Quotient Mappings

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set.

Let $\mathcal R_1$ be an equivalence on $S$, and $\mathcal R_2$ be an equivalence on the quotient set $S / \mathcal R_1$.


We can find an equivalence $\mathcal R_3$ on $S$ such that $\paren {S / \mathcal R_1} / \mathcal R_2$ is in one-to-one correspondence with $S / \mathcal R_3$ under the mapping:

$\phi: \paren {S / \mathcal R_1} / \mathcal R_2 \to S / \mathcal R_3: \eqclass {\eqclass x {\mathcal R_1} } {\mathcal R_2} \mapsto \eqclass x {\mathcal R_3}$.


Proof

Define $\mathcal R_3$ to be the equivalence induced by:

$x \mapsto \eqclass {\eqclass x {\mathcal R_1} } {\mathcal R_2}$

By definition of $\mathcal R_3$:

$\eqclass {\eqclass x {\mathcal R_1} } {\mathcal R_2} = \eqclass {\eqclass y {\mathcal R_1} } {\mathcal R_2} \implies \eqclass x {\mathcal R_3} = \eqclass y {\mathcal R_3}$

Therefore, $\phi$ is well-defined.


Again by definition of $\mathcal R_3$:

$\eqclass x {\mathcal R_3} = \eqclass y {\mathcal R_3} \implies \eqclass {\eqclass x {\mathcal R_1} } {\mathcal R_2} = \eqclass {\eqclass y {\mathcal R_1} } {\mathcal R_2}$

which means $\phi$ is an injection.


Lastly, note that every element of $S / \mathcal R_3$ is of the form $\eqclass x {\mathcal R_3}$ for some $x \in S$.

It is now immediate from the definition of $\phi$ that it is surjective.


Hence $\phi$ is a bijection, as desired.

$\blacksquare$


Sources