Surjection iff Right Inverse

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.


A right inverse of $f$ is in general not unique.

Uniqueness occurs if and only if $f$ is a bijection.

Proof 1

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.


Proof 2

Take the result Condition for Composite Mapping on Right:

Let $A, B, C$ be sets.

Let $f: B \to A$ and $g: C \to A$ be mappings.


$\Img g \subseteq \Img f$

if and only if:

$\exists h: C \to B$ such that $h$ is a mapping and $f \circ h = g$.

Let $C = A = T$, let $B = S$ and let $g = I_T$.

Then the above translates into:

$\Img {I_T} \subseteq \Img f$

if and only if:

$\exists g: T \to S$ such that $g$ is a mapping and $f \circ g = I_T$.

But we know that:

$\Img f \subseteq T = \Img {I_T}$

So by definition of set equality, the result follows.


Axiom of Choice

This theorem 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.

Also see