First-order Peano Arithmetic

Q is Σ 1 -complete, a fact which will turn out to be very important. But, as we saw, in other ways Q is an extremely weak theory. To derive elementary general truths like ∀x(0 + x = x) that are beyond Q's reach, we obviously will have to use a formal arithmetic that incorporates some stronger axiom(s) for proving quantified wffs. This chapter explains the induction axioms we need to add, working up to the key theory PA, first-order Peano Arithmetic . Induction and the Induction Schema (a) In informal argumentation, we frequently appeal to the following principle of mathematical induction in order to prove general claims: Suppose (i) 0 has the numerical property P . And suppose (ii) for any number n , if it has P , then its successor n + 1 also has P . Then we can conclude that (iii) every number has property P . In fact, we used informal inductions in the last chapter. For example, to prove that Q correctly decides all Σ 1 wffs, we in effect began: let n have the property P if Q-correctly-decides-Σ 1 -wffs-of-degree-no-more-than n . Then we argued (i) 0 has property P , and (ii) for any number n , if it has P , then n + 1 also has P . So we concluded (iii) every number has P , i.e. Q correctly decides any Σ 1 wff, whatever its degree.