Prove the function
$f:\mathbb{N} \to\mathbb{N}$
defined by $f(x)=2^x$ for all $x$ in $\mathbb{N}$ is one to one.
Is my proof correct and if not what errors are there.

For all $x_1,x_2$ $\in$$N$, if $f(x_1)=f(x_2)$, then $x_1=x_2$
Assume $f(x_1)=f(x_2)$ and show $x_1=x_2$
$x_1=x_2$ , which means $f$ is injective.

  • 1
    $\begingroup$ You may want to apply induction here (since you're supposed to be writing a proof, not just stating facts). $\endgroup$ Nov 25, 2014 at 4:14
  • $\begingroup$ Well the question asked for me to prove the statement.Is what i did not a proof? I just used contrapositive. Would this affect how the question will be marked? $\endgroup$
    – IT ken
    Nov 25, 2014 at 4:53

1 Answer 1


Looks like you got it down. I don't see any errors in comprehension; just a little redundancy in the layout of the proof. If I were to make changes I would completely do away with the line "For all $x_1,x_2$ $\in$$N$, if $f(x_1)=f(x_2)$, then $x_1=x_2$ $f(x)=2^x$" then edit the rest of your proof to read

"Assume $f(x_1)=f(x_2)$. Then $$2^{x_1}=2^{x_2} \\ \implies \frac{2^{x_1}}{2^{x_1}} = \frac{2^{x_2}}{2^{x_1}} \\ \implies 1 = 2^{x_2-x_1}$$ And we know $a^b = 0$ whenever $a \neq 0$ and $b = 0$. Hence, $x_1-x_2=0$ so $f$ is one-to-one."

  • $\begingroup$ @graydad does this kind of assume that we know inverse, $\log_2$ is injective? $\endgroup$
    – Kamster
    Nov 25, 2014 at 4:33
  • $\begingroup$ @Kamster erm... possibly? Depends on what OP is allowed to use to complete this proof. I'll edit my answer to be on the safe side. $\endgroup$
    – graydad
    Nov 25, 2014 at 4:37
  • $\begingroup$ yea it just seemed weird sometimes in injective proofs to use the inverse function. But then again I couldnt think explicitly how to do it other wise $\endgroup$
    – Kamster
    Nov 25, 2014 at 4:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .