Surjection from Natural Numbers iff Right Inverse

From ProofWiki
Jump to navigation Jump to search

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: f^{-1} \left({x}\right)$ is non-empty

where $f^{-1} \left({x}\right)$ 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: g \left({x}\right) = \min \left( f^{-1} \left({x}\right) \right)$

By the definition of a smallest element, it follows that:

$\forall x \in S: g \left({x}\right) \in f^{-1} \left({x}\right)$

That is:

$\forall x \in S: f \left({g \left({x}\right)}\right) = \left({f \circ g}\right) \left({x}\right) = x$

In other words, $g$ is a right inverse of $f$.

$\blacksquare$


Also see