Theory of Computation

1.5   WHY INDUCTION TICKS

Induction is neat, but is it a valid principle? Why should we believe such a thing? Unfortunately, the previous section does not shed much light other than the somewhat surprising equivalence of the two induction principles with the least principle.

It turns out that we cannot prove either of the three as valid from any substantially simpler and therefore more readily believable facts of arithmetic. We can build a plausible case, however. Given the equivalence of the three, let us use simple induction as the pivot of our plausibility argument.

Simple induction is, intuitively, a proof generator that, for each given property (n), certifies the latter’s validity for any n that we want: Recall that the combination of the I.H. and I.S. establish for the arbitrary n, that if (n) is valid, then so is (n + 1). Thus given the starting point, that is, the validity of (0), we can certify the validity of (1). And then of (2). If we repeat this process—of inferring the truth ...