How to prove that $a_n=2^n$ is not onto?

Question

The domain and codomain of the sequence $a$ is $\mathbb N$. I understand that the simplest way to prove that it is not onto is to simply give a counterexample. However, how would I prove it in a more rigorous way? Here is what I have so far. $y=a_n=2^n\implies n=log_2(y)$.

However, if you plug this back into the sequence (the way my class has been proving surjective functions), you just end up with $y$, which would mean that it is onto. I feel like I'm somehow missing the fact that we have restricted the codomain to natural numbers, but how would I be able to show it?

Answer 1

An alternative approach is to recognize that if you arrange the domain in ascending order (i.e. $\{1,2,3,\cdots\}$) then the corresponding range (i.e. codomain) will also be in ascending order (i.e. $\{2^1, 2^2, 2^3, \cdots\}$).

This is because $0 < x < y \implies 2^x < 2^y.$

Therefore, the mapping will be onto if and only if, when the codomain is arranged in ascending order, and expressed as $\{b_1, b_2, b_3, \cdots\},$ the set happens to satisfy both of the following constraints:

• $b_1 = 1$.
• $b_{n+1} = b_n + 1 ~: ~n \in \Bbb{Z^+}$.

So, by reasoning that (for example), you don't generally have that $2^{n+1} - 2^n = 1$, you can infer that the mapping is not onto.

Answer 2

All $a_n$ are even numbers (except $a_0 = 1$ if you understand that $0 \in \mathbb N$).