

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
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. – Trevor Wilson Jan 24 '13 at 3:06
By the way, I think "inverse problems" means something different, so I removed the tag. – Trevor Wilson Jan 24 '13 at 3:09
up vote 1 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


