# Why is this mapping from binary to natural numbers surjective?

In my Lecture we came across something of importance for the Church-Turing-Thesis and i noticed one particular function, which confused me.

Function: Let $$bin(x)$$ be the injective binary extension without leading zeros. It is not surjective because of the extension without leading zeros.

$$cod := \{0,1\}^* \to \mathbb{N} \hspace{2mm} x \mapsto bin^{-1}(1x)-1$$

Question:

Why is this particular map from the binaries and the natural numbers surjective ? I do not need a intricate proof, but a explanation is enough to wrap my head around this topic.

They also noted that $$bin^{-1}$$ can be written, because 1x is in the image of $$bin$$.

Injectivity is given, because $$bin$$ is injective and on two different strings $$x$$ and $$y$$ we get two different decimal numbers out of the function.

Thanks in advance for any awnser on this question, or any comments posted on it.

For any number $$n\in\mathbb{N}$$, consider $$bin(n+1)$$. Since $$n+1>0$$, there must be at least one bit in $$bin(n+1)$$ in the state of "1".
Its not too hard to see why this immediately implies that there exists some $$x\in \{0,1\}^*$$ such that $$bin(n+1)=1x$$ (since we can remove the trailing zeros), and hence $$n+1={bin}^{-1}(1x)$$, meaning that $$n={bin}^{-1}(1x)-1=cod(x)$$.
Therefore $$cod$$ is surjective by definition.