Completeness theorems, incompleteness theorems and models of arithmetic

Abstract:

Let $\mathcal {A}$ be a consistent extension of Peano arithmetic and let $\mathcal {A}_n^0$ denote the set of $\Pi _n^0$ consequences of $\mathcal {A}$. Employing incompleteness theorems to generate independent formulas and completeness theorems to construct models, we build nonstandard models of $\mathcal {A}_{n + 2}^0$ in which the standard integers are $\Delta _{n + 1}^0$-definable. We thus pinpoint induction axioms which are not provable in $\mathcal {A}_{n + 2}^0$; in particular, we show that (parameter free) $\Delta _1^0$-induction is not provable in Primitive Recursive Arithmetic. Also, we give a solution of a problem of Gaifman on the existence of roots of diophantine equations in end extensions and answer questions about existentially complete models of $\mathcal {A}_2^0$. Furthermore, it is shown that the proof of the Gödel Completeness Theorem cannot be formalized in $\mathcal {A}_2^0$ and that the MacDowell-Specker Theorem fails for all truncated theories $\mathcal {A}_n^0$.