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?



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$.

  • $\begingroup$ Or sufficiently small $x$ and $x+1$. $\endgroup$ – egreg Mar 19 '15 at 23:04
  • $\begingroup$ What... $2$ is very large! $\endgroup$ – Asaf Karagila Mar 19 '15 at 23:05

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. $$

  • $\begingroup$ Thank you for the solution. I do have some further questions. Like, where did the 2^(n-1) <= x < 2^n come from? Or how did you know to take f(s^(n-1)) to get n? This is all just confusing to me. $\endgroup$ – generic user007 Mar 19 '15 at 23:49
  • $\begingroup$ @DietDrPepsi Do you know the binary system? $\endgroup$ – egreg Mar 19 '15 at 23:54
  • $\begingroup$ As in 1's and 0's? I apologize for my lack of knowledge. It's kind of difficult to learn when my professor is incompetent and we basically have to try to teach ourselves. Are you meaning like a binary system as in where a function has two arguments? $\endgroup$ – generic user007 Mar 20 '15 at 0:00
  • $\begingroup$ @DietDrPepsi No, to the representation of numbers using only the digits $0$ and $1$. $\endgroup$ – egreg Mar 20 '15 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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