Is the mapping from bits to ints one to one and onto?

Question

Is the mapping of the set of binary numbers (defined as character sequences, e.g. $0, 1, 10, 11, ....$) to the set of non-negative integers (e.g. $0, 1, 2, 3...$) one to one and onto?

It's clear that $0$ in binary maps to $0$ in the integers, $1$ in binary maps to $1$ in the set of integers, and $10$ in binary maps to the integer $2$, and so on, but does this trend of one to one and onto mapping hold as both sets approach infinity?

Answer 1

HINT

To prove this mathematically, you should mathematically define the mapping you are talking about. So, define the function $f:B \mapsto \mathbb{N}$ from the set of binary strings $B$ to the set of natural numbers (non-negative integers) $\mathbb{N}$ as follows:

Where $b$ is a bitstring $b_n b_{n-1} ... b_1 b_0$:

$$f(b)= \sum_{i=0}^n b_i \cdot 2^i$$

With this, you should be able to rigorously prove that $f$ is injective and surjective.

Answer 2

If you map any sequence of things to any other sequence of things in a way that the $n$th thing is mapped to the $n$th of the other things, the map will be a bijection. So: yes!

Answer 3

Short answer: Yes.

Long answer: Yes, 0 isn't a positive integer but provided you correct this it'll be bijective. Prove this.

Answer 4

You did not specify which mapping, but according to you description, you are talking about the following mapping:

$$x=\sum a_i \times 10^i = \sum b_i \times 2^i$$

Notice both $x= \sum a_i \times 10^i$ and $x= \sum b_i \times 2^i$ are unique representation for $x$, and thus the mapping between the two representation of $x$, $\sum a_i \times 10^i = \sum b_i \times 2^i$ is also unique - thus the answer is yes.