The need for the axiom of choice is to choose arbitrary elements. Injectivity eliminates this need.
Assume that $A$ is not empty, if $f\colon A\to B$ is injective this means that if $b\in B$ is in the range of $f$ then there is a unique $a\in A$ such that $f(a)=b$.
This means that we can define (from $f$) what is the $a$ to which we send $b$.
So if $f$ is not onto $B$ we have two options:
- $b\in B$ in the range of $f$, then we have exactly one option to send $b$ to.
- $b\in B$ not in the range of $f$. Since $A$ is not empty fix in advance some $a_0\in A$ and send $b$ to $a_0$.
Another way to see this is let $B=B'\cup Rng(f)$, where $B'\cap Rng(f)=\varnothing$. Fix $a_0\in A$ and define $g|_{B'}(x)=a_0$. For every $b\in Rng(f)$ we have that $f^{-1}[\{b\}]=\{a\in A\mid f(a)=b\}$ is a singleton, so there is only one function which we can define in: $$\prod_{b\in Rng(f)}f^{-1}[\{b\}]$$
Now let the unique function in the product be $g|_{Rng(f)}$ and define $g$ to be the union of these two.
Your intuition about the need for the axiom of choice is true for surjections, if $f$ was surjective then we only know that $f^{-1}[\{b\}]$ is non-empty for every $b\in B$, and we need the full power of the axiom of choice to ensure that an arbitrary surjection has an inverse function.
To the edited question:
The axiom of choice is needed because we have models in which the axiom of choice does not hold, where there exists an infinite family of pairs whose product is empty.
There are weaker forms from which follow choice principles for finite sets. However these are still not provable from ZF on its own.
As indicated by Chris Eagle in the comments, and as I remark above, in a product of singletons there is no need for the axiom of choice since there is only one way to choose from a singleton.
Further reading:
- Finite choice without AC
- axiom of choice: cardinality of general disjoint union
Let $f:X\to\Bbb N$ be your injection. Let $M=f[X]$. First define a bijection $g:\Bbb N\to M$ recursively as follows. First, $g(0)=\min M$. If $n\in\Bbb Z^+$, and $g(k)$ has been defined for $k<n$, let $$g(n)=\min\Big(M\setminus\{g(0),\dots,g(n-1)\}\Big)\;.$$ It’s straightforward to verify by induction that $g$ is a bijection.
Added: First, it’s clear that $g$ is injective, since the construction ensures that if $m<n$, then $g(n)\ne g(m)$. To show that $g$ is surjective, it suffices to show that for each $n\in\Bbb N$, $$\{g(k):k<n\}=\{m\in M:m<g(n)\}\;:\tag{1}$$ this ensures that each member of $M$ less than $g(n)$ is already ‘hit’ by the function $g$, so $g$ has no ‘holes’ in its range.
$(1)$ is trivially true for $n=0$: both sides are empty. Suppose that it holds for some $n\in\Bbb N$; we want to show that $\{g(k):k\le n\}=\{m\in M:m\le g(n)\}$. It’s clear that $\{g(k):k\le n\}\subseteq\{m\in M:m\le g(n)\}$, so suppose that $m\in M$, $m\le g(n)$, and $m\notin\{g(k):k\le n\}$. Then $m<g(n)$, and $m\notin\{g(k):k<n\}$, contradicting the definition of $g(n)$ as the smallest member of $M$ not in $\{g(k):k<n\}$. $\dashv$
Since $f$ is an injection, it’s a bijection from $X$ to $M$, and $f^{-1}$ is a bijection from $M$ to $X$. We now have
$$\Bbb N\overset{g}\longrightarrow M\overset{f^{-1}}\longrightarrow X\;,$$
where each of the maps is a bijection, so their composition is a bijection from $\Bbb N$ to $X$.
Best Answer
There is no really elementary proof, since this is in fact independent of the "constructive" part of the usually axioms of set theory.
However if one has a basic understanding of the axiom of choice then one can easily construct the injection. The axiom of choice says that if we have a family of non-empty sets then we can choose exactly one element from each set in our family.
Suppose that $g\colon Y\to X$ is a surjection then for every $x\in X$ there is some $y\in Y$ such that $g(y)=x$. I.e., the set $\{y\in Y\mid g(y)=x\}$ is non-empty.
Now consider the family $\Bigg\{\{y\in Y\mid g(y)=x\}\ \Bigg|\ x\in X\Bigg\}$, by the above sentence this is a family of non-empty sets, and using the axiom of choice we can choose exactly one element from every set. Let $y_x$ be the chosen element from $\{y\in Y\mid g(y)=x\}$. Let us see that the function $f(x)=y_x$ is injective.
Suppose that $y_x=y_{x'}$, in particular this means that both $y_x$ and $y_{x'}$ belong to the same set $\{y\in Y\mid g(y)=x\}$ and this means that $x=g(y_x)=g(y_{x'})=x'$, as wanted.
Some remarks:
The above proof uses the full power of the axiom of choice, we in fact construct an inverse to the injection $g$. However we are only required to construct an injection from $X$ into $Y$, which need not be an inverse of $g$ -- this is known as The Partition Principle:
It is still open whether or not the partition principle implies the axiom of choice, so it might be possible with a bit less than the whole axiom of choice.
However the axiom of choice is definitely needed. Without the axiom of choice it is consistent that there exist two sets $X$ and $Y$ such that $Y$ has both an injection into $X$ and a surjection onto $X$, but there is no injection from $X$ into $Y$.