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: \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