In elementary accounts, one sometimes sees a rigid n → n + 1 approach to induction, the common induction principle, asserting that if 0 has a certain property, and if that property is transferred from every number n to n + 1, then every natural number has that property. That is, if P0 ∧∀n(Pn ⟹ Pn + 1), then ∀n Pn. The strong induction principle, in contrast, asserts that if we have a property P of natural numbers, with the feature that a number has that property whenever all smaller numbers have it, then indeed every number has that property. That is, if ∀n [(∀k < n Pk) ⟹ Pn], then ∀n Pn. The
...more
