Surjection from Natural Numbers iff Right Inverse
Theorem
Let $S$ be a set.
Let $f: \N \to S$ be a mapping, where $\N$ denotes the set of natural numbers.
Then $f$ is a surjection if and only if $f$ admits a right inverse.
Proof
Necessary Condition
Suppose that $g: S \to \N$ is a right inverse of $f$.
That is, let $f \circ g = I_S$, the identity mapping on $S$.
We have that $I_S$ is a surjection.
By Surjection if Composite is Surjection, it follows that $f$ is a surjection.
$\Box$
Sufficient Condition
Now, suppose that $f: \N \to S$ is a surjection.
By the definition of a surjection, it follows that:
- $\forall x \in S: \map {f^{-1} } x$ is non-empty
where $\map {f^{-1} } x$ denotes the preimage of $x$ under $f$.
From the Well-Ordering Principle, $\N$ is well-ordered.
Hence, we can define the mapping $g: S \to \N$ as:
- $\forall x \in S: \map g x = \map \min {\map {f^{-1} } x}$
By the definition of a smallest element, it follows that:
- $\forall x \in S: \map g x \in \map {f^{-1} } x$
That is:
- $\forall x \in S: \map f {\map g x} = \map {\paren {f \circ g} } x = x$
In other words, $g$ is a right inverse of $f$.
$\blacksquare$
Also see
- Surjection iff Right Inverse, which depends on the axiom of choice.