# Is proof of totality of a semantic function for binary numbers cicular?

I think the following proof found in a textbook is circular, since the proof for case n=n'0 assumes the case n=n'1 and vice versa. Am I missing something?

Proof that the semantic function N is a total function from binary strings into the integers:

Let N be defined thusly:

N(0) = 0; N(1) = 1; N(n0) = 2*N(n); N(n1) = 2*N(n) + 1;

For any n, there is one and only on integer mapped to by N(n), that is to say, N is a total function from binary strings into the integers. (A)

In the case n = 0, there is only one way to evaluate N(n) and that is with N(n) = N(0) = 0; hence (A) clearly holds. The proof for the case n = 1 is similar.

In the case n = n'0, we have only one way to evaluate N(n) and that is with N(n) = N(n'0) = 2*N(n'). Assuming by induction that (A) holds for N(n'), (A) clearly holds for N(n). The proof for n = n'1 is similar.

QED

In the second part of the proof, for the case n = n'0 you have to assume for induction that * holds for n = n'1, and vice versa. Does this not lead to a circular dependency in the proof?

• For $N(n0)$ you have to assume that the statement holds for $N(n'1)$ where $n'$ is shorter than $n$, so that's alright. – Karolis Juodelė Jun 7 '14 at 5:24
• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Jun 7 '14 at 7:06
• Wohoo, we have another example for why writing down proofs rigorously is very important in teaching. – Raphael Jun 11 '14 at 9:53

The proof is by induction on the length of the string. You're proving the inductive claim for all strings of length $n$, both those terminating in $0$ and those terminating in $1$. The proof goes by considering these two cases, but you're assuming and proving the inductive hypothesis for all strings of a particular length at once.