Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To 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|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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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