Surjective and Not Injective Problem for this data structures homework I am having a hard time figuring out this one problem on surjection and injection. Here is the problem:
Show that each function $f\colon \mathbb{N} \rightarrow \mathbb{N}$ has the listed properties.
$f(x) = \operatorname{ceiling}(\log_2 (x+1))$ is Surjective and not injective.
For problems dealing with injection I know you are supposed to show $f(x) = f(y)$ so that $x = y$ where each element in $x$ points to a specific element in $f(x)$, I think? I am just not sure how to simplify this problem down since it is dealing with ceilings and logs to show that $f(x) \neq f(y)$ since this problem is not injective. As far as showing surjection, I am not clear on how to do that. My professor is not very clear. Any tips on what to do or any explanation on how to calculate surjection?
Thanks
 A: To show that this is not injective, you have to show that for some $x\neq y$ you have $f(x)=f(y)$.
HINT: Look at sufficiently large $x$ and $x+1$.
To show that this function is surjective, you need to show that for every $n\in\Bbb N$, there is some $x$ such that $f(x)=n$.
HINT: Remember that $\operatorname{ceiling}(n)=n$.
A: Let's try our hand with some numbers and a calculator: $f(0)=0$, $f(1)=1$,
\begin{align}
f(2)&=\lceil\log_2(3)\rceil=2\\
f(3)&=\lceil\log_2(4)\rceil=2\\
f(4)&=\lceil\log_2(5)\rceil=3\\
f(5)&=\lceil\log_2(6)\rceil=3\\
f(6)&=\lceil\log_2(7)\rceil=3\\
f(7)&=\lceil\log_2(8)\rceil=3\\
f(8)&=\lceil\log_2(9)\rceil=4
\end{align}
that should make us suspect that $f(x)$ is the number of digits in the binary representation of $x$ (the value $f(0)=0$ is accurate, because the length of the binary representation of $0$ is zero, we write it $0$ just to “see” it).
Now a number $x$ has $n$ digits in its decimal representation if and only if $2^{n-1}\le x<2^n$, which can also be written as $2^{n-1}<x+1\le 2^n$ so $n-1<\log_2(x+1)\le n$ that entails $\lceil\log_2(x)\rceil=n$. Write down also the converse.
Thus the map is surjective, because $f(2^n-1)=n$, while $f(2)=f(3)$ so $f$ is not injective. Note that we don't need to compute the logarithm for concluding this.
Even if you couldn't see what the function represents, you could still show $f(2)=f(3)$. Indeed, $2<2+1<4$, so $1<\log_2(2+1)<2$ and therefore $\lceil\log_2(2+1)\rceil=2$. For $f(3)$ there are even less remarks to do:
$$
f(3)=\lceil\log_2(3+1)\rceil=\lceil2\rceil=2.
$$
