Quotient Theorem for Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

Any mapping $f: S \to T$ can be uniquely factored into a surjection, followed by a bijection, followed by an injection.

Thus:

$f = i \circ r \circ q_{\mathcal R_f}$

where:

$q_{\mathcal R_f}: S \to S / \mathcal R_f : \map {q_{\mathcal R_f} } s = \eqclass s {\mathcal R_f}$
$r: S / \mathcal R_f \to \Img f: \map r {\eqclass s {\mathcal R_f} } = \map f s$
$i: \Img f \to T: \map i t = t$


This can be illustrated using a commutative diagram as follows:

$\begin {xy} \[email protected] + [email protected] + 1em { S \[email protected]{-->}[rrr]^*{f = i_T \circ r \circ q_{\mathcal R_f} } \ar[d]_*{q_{\mathcal R_f} } & & & T \\ S / \mathcal R_f \ar[rrr]_*{r} & & & \Img f \ar[u]_*{i_T} } \end {xy}$


Proof

From Factoring Mapping into Surjection and Inclusion, $f$ can be factored uniquely into:

A surjection $g: S \to \Img f$, followed by:
The inclusion mapping $i: \Img f \to T$ (an injection).


$\begin{xy}\[email protected][email protected]+1em { S \ar[drdr]_*{g} \[email protected]{-->}[rr]^*{f = i_T \circ g} & & T \\ \\ & & \Img f \ar[uu]_*{i_T} }\end{xy}$


From the Quotient Theorem for Surjections, the surjection $g$ can be factored uniquely into:

The quotient mapping $q_{\mathcal R_f}: S \to S / \mathcal R_f$ (a surjection), followed by:
The renaming mapping $r: S / \mathcal R_f \to \Img f$ (a bijection).


Thus:

$f = i_T \circ \paren {r \circ q_{\mathcal R_f} }$

As Composition of Mappings is Associative it can be seen that $f = i_T \circ r \circ q_{\mathcal R_f}$.


The commutative diagram as follows:

$\begin {xy} \[email protected] + [email protected] + 1em { S \[email protected]{-->}[rrr]^*{f = i_T \circ r \circ q_{\mathcal R_f} } \ar[ddd]_*{q_{\mathcal R_f} } \[email protected]{..>}[drdrdr]_*{g = r \circ q_{\mathcal R_f} } & & & T \\ \\ \\ S / \mathcal R_f \ar[rrr]_*{r} & & & \Img f \ar[uuu]_*{i_T} } \end {xy}$


$\blacksquare$


Also known as

Otherwise known as the factoring theorem or factor theorem.


This construction is known as the canonical decomposition of $f$.


Also see


Sources