2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Karolis Juodelė Jun 7 '14 at 5:24
  • 1
    $\begingroup$ 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. $\endgroup$ – FrankW Jun 7 '14 at 7:06
  • 1
    $\begingroup$ Wohoo, we have another example for why writing down proofs rigorously is very important in teaching. $\endgroup$ – Raphael Jun 11 '14 at 9:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Although it wasn't clear to me what you meant at first it became so on reflection. Just in case anyone wanders across this page in future, you are assuming the hypothesis for both n = n'0 and n = n'1, however n' is shorter than n in both cases. So long as you have a base case for both forms which n could take (for strings of the same length), you can prove the proposition for both n=n'0 and n = n'1 by induction; and in turn prove it for m=n0 or m = n1, and so on. PS. I apologize for not using LateX, I intend to learn it but thought it best to confirm that my problem is resolved first. $\endgroup$ – Dion Bridger Jun 10 '14 at 12:44

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.