End extensions of models of arithmetic.
James H. Schmerl · Notre Dame Journal of Formal Logic · 1992
A concise proof is presented of Wilkie's Theorem that for every model of Peano Arithmetic there is a diophantine equation having no solution in that model but having a solution in some end extension of that model.Kaufmann (in [2]) observed that the Completeness Theorem formalized in Peano Arithmetic can be used to give an alternate proof of the MacDowell-Specker Theorem on elementary end extensions of models of PA. (See Theorem 3 for an outline of his proof.)Rabin [4] proved that every model cM of PA has an elementarily equivalent extension which solves a Diophantine equation having coefficients in M but having no solution in M. Gaifman [1] asked whether Rabin's Theorem could be improved by requiring that the extension be an end extension.By Matijasevic's solution to Hubert's Tenth Problem, which was unavailable to Rabin, Gaifman's question is equivalent to asking whether every model of PA has an elementarily equivalent end extension which is not a Σ r extension.After several partial results had been obtained (Manevitz [3], Wilkie [6]), Wilkie [7] proved a comprehensive theorem which yielded an affirmative answer to Gaifman's question.His proof relied heavily on his previously obtained affirmative answer for countable models.In this note we will give a rather quick and direct proof of Wilkie's theorem along the lines of Kaufmann's proof of the MacDowell-Specker Theorem.Notation and terminology will be that standardly used in the Peano Arithmetic literature.The language L of PA is finite.For cM an L-structure, L(M) is L augmented by constant symbols for elements of M. Note that Σ n and U n are sets of Lrformulas (or L(M)-formulas) which have a certain syntactic form.For an L-structure cM, we let D( (cN).We let SSy(cM) be the standard system of cM; and for a complete theory ΓΞ2 PA, we let Rep(Γ) be the standard system of its minimal model.Given a model cM of PA and an L-structure cM, we say that cM is internal to