2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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