Surjection iff Right Inverse/Proof 1

From ProofWiki
Jump to navigation Jump to search


A mapping $f: S \to T, S \ne \O$ is a surjection if and only if:

$\exists g: T \to S: f \circ g = I_T$


$g$ is a mapping
$I_T$ is the identity mapping on $T$.

That is, if and only if $f$ has a right inverse.


Assume $\exists g: T \to S: f \circ g = I_T$.

From Identity Mapping is Surjection, $I_T$ is surjective, so $f \circ g$ is surjective.

So from Surjection if Composite is Surjection, $f$ is a surjection.

Note that the existence of such a $g$ requires that $S$ is non-empty.

Now, assume $f$ is a surjection.

Consider the indexed family of non-empty sets $\set {\map {f^{-1} } y}_{y \mathop \in T}$ where $\map {f^{-1} } y$ denotes the preimage of $y$ under $f$.

Using the axiom of choice, there exists a mapping $g: T \to S$ such that $\map g y \in \set {\map {f^{-1} } y}$ for all $y \in T$.


That is, $\map {\paren {f \circ g} } y = y$, as desired.


Axiom of Choice

This proof depends on the Axiom of Choice.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.