Prove: There exists a map $f:\mathbb{N}\to\mathbb{N}$ that is injective, but not surjective.
I immediately thought of the function $f(x)=2x$
It is trivial to prove the "not surjective part" since the "range" of $f$ is even natural number, which is a subset of natural number.
However, I am not sure how to prove my $f$ is injective.
The inverse function of $f$, $f^{-1}(y)=y/2$, is what came to my mind, but am I allow to do "it"?
To be precisely, how do I "work it out" using something basic things(such as axioms)?
It just seemed to me that calculating an inverse function and asking the reader to believe the function "works" is difficult for them to swallow since an inverse function is nothing basic/obvious.
Best Answer
The standard way to show injectivity is to assume $f(x_1)=f(x_2)$. Then, by definition of $f$, we have $2x_1=2x_2$. Since $\mathbb{N}$ has the cancellation law, we can say $x_1=x_2$ and we conclude $f$ is injective.