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.

  • $\begingroup$ As a function from $\mathbb{N}$ to the set of even numbers, $f$ has a (two-sided) inverse as you claim, but as a function $\mathbb{N} \to \mathbb{N}$ it only has a left inverse. $\endgroup$ – Trevor Wilson Jan 24 '13 at 3:06
  • $\begingroup$ By the way, I think "inverse problems" means something different, so I removed the tag. $\endgroup$ – Trevor Wilson Jan 24 '13 at 3:09

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.


To prove it is injective, it is usually easiest to simply verify the definition: Let $x$ and $y$ be distinct elements of the domain and prove that $f(x) \ne f(y)$.

This does not require the notion of a left or right inverse.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.