I think the following proof found in a textbook is circular, since the proof for
ID: 651845 • Letter: I
Question
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?
Explanation / Answer
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.