Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Completeness theorems, incompleteness theorems and models of arithmetic

Author: Kenneth McAloon
Journal: Trans. Amer. Math. Soc. 239 (1978), 253-277
MSC: Primary 03H15; Secondary 03F30
MathSciNet review: 487048
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

  • [B] Jon Barwise, Infinitary methods in the model theory of set theory, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969), North-Holland, Amsterdam, 1971, pp. 53–66. MR 0277370
  • [Fef] S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960/1961), 35–92. MR 0147397
  • [Fr] Harvey Friedman, Some applications of Kleene’s methods for intuitionistic systems, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Springer, Berlin, 1973, pp. 113–170. Lecture Notes in Math., Vol. 337. MR 0376310
  • [G] Haim Gaifman, A note on models and submodels of arithmetic, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Springer, Berlin, 1972, pp. 128–144. Lecture Notes in Math., Vol. 255. MR 0419215
  • [G, bis] Haim Gaifman, Uniform extension operators for models and their applications, Sets, Models and Recursion Theory (Proc. Summer School Math. Logic and Tenth Logic Colloq., Leicester, 1965) North-Holland, Amsterdam, 1967, pp. 122–155. MR 0220586
  • [G, K, T] R. O. Gandy, G. Kreisel, and W. W. Tait, Set existence, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 577–582. MR 0159747
  • [G, M, S] D. C. Goldrei, A. Macintyre, and H. Simmons, The forcing companions of number theories, Israel J. Math. 14 (1973), 317–337. MR 0327511
  • [H, B] D. Hilbert and P. Bernays, Grundlagen der Mathematik. II, Zweite Auflage. Die Grundlehren der mathematischen Wissenschaften, Band 50, Springer-Verlag, Berlin-New York, 1970 (German). MR 0272596
  • [H, W] Joram Hirschfeld and William H. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Mathematics, Vol. 454, Springer-Verlag, Berlin-New York, 1975. MR 0389581
  • [K, L] G. Kreisel and A. Lévy, Reflection principles and their use for establishing the complexity of axiomatic systems, Z. Math. Logik Grundlagen Math. 14 (1968), 97–142. MR 0228333
  • [K, M] Jean-Louis Krivine and Kenneth McAloon, Forcing and generalized quantifiers, Ann. Math. Logic 5 (1972/73), 199–255. MR 0446890
  • [K, M, bis] J. L. Krivine and K. McAloon, Some true unprovable formulas for set theory, The Proceedings of the Bertrand Russell Memorial Conference (Uldum, 1971), Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 332–341. MR 0357112
  • [K, T] G. Kreisel and G. Takeuti, Formally self-referential propositions for cut free classical analysis and related systems, Dissertationes Math. (Rozprawy Mat.) 118 (1974), 55. MR 0384497
  • [K, W] G. Kreisel and Hao Wang, Some applications of formalized consistency proofs, Fund. Math. 42 (1955), 101–110. MR 0073539
  • [Man] Larry Michael Manevitz, Internal end-extensions of Peano arithmetic and a problem of Gaifman, J. London Math. Soc. (2) 13 (1976), no. 1, 80–82. MR 0441722
  • [Ma] Ju. V. Matijasevič, Eunumerable sets are diophantine, Dokl. Akad. Nauk SSSR 191 (1970), 279-282 = Soviet Math. Dokl. 11 (1970), 354-358. MR 41 #3390.
  • [Mc] Kenneth McAloon, Applications alternées de théorèmes d’incomplétude et de théorèmes de complétude, C. R. Acad. Sci. Paris Sér. A-B 280 (1975), no. 13, Ai, A849–A852 (French, with English summary). MR 0369059
  • [Mc, bis] Kenneth McAloon, Formules de Rosser pour 𝑍𝐹, C. R. Acad. Sci. Paris Sér. A-B 281 (1975), no. 16, Ai, A669–A672 (French, with English summary). MR 0384543
  • [Mc, ter] -, Consistency statements and number theories, Proc. 1975 Logic Colloq. at Clermont-Ferrand (M. Guillaume, Editor), Publ. C.N.R.S., 1977.
  • [M, Sp] R. Mac Dowell and E. Specker, Modelle der Arithmetik, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 257–263 (German). MR 0152447
  • [M, S] A. Macintyre and H. Simmons, Algebraic properties of number theories, Israel J. Math. 22 (1975), no. 1, 7–27. MR 0398820
  • [Mon] R. Montague, Semantical closure and non-finite axiomatizability. I, Infinitistic Methods, Pergamon, Oxford; PWN, Warsaw, 1961, pp. 45-69. MR 27 #38. MR 0150033 (27:38)
  • [Mos] A. Mostowski, On models of axiomatic systems, Fund. Math. 39 (1952), 133-158. (1953) MR 14, 938. MR 0054547 (14:938c)
  • [Mos, bis] -, A generalization of the incompleteness theorem, Fund. Math. 49 (1960/61), 205-232. MR 24 # A41. MR 0130174 (24:A41)
  • [Ra] Michael O. Rabin, Non-standard models and independence of the induction axiom, Essays on the foundations of mathematics, Magnes Press, Hebrew Univ., Jerusalem, 1964, pp. 287–299. MR 0161795
  • [Rog] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
  • [Ros] J. B. Rosser, Extensions of some theorems of Gödel and Church, J. Symbolic Logic 1 (1936), 89-91.
  • [Ry] C. Ryll-Nardzewski, The role of the axiom of induction in elementary arithmetic, Fund. Math. 39 (1952), 239–263 (1953). MR 0054546
  • [Sch] Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
  • [Sco] Dana Scott, On constructing models for arithmetic, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 235–255. MR 0152445
  • [Sim] H. Simmons, Existentially closed structures, J. Symbolic Logic 37 (1972), 293–310. MR 0376342
  • [Sm] C. A. Smoryński, Applications of Kripke models, Metamathematical investigation of intuitionistic arithmetic and analysis, Springer, Berlin, 1973, pp. 324–391. Lecture Notes in Mathematics, Vol. 344. MR 0444442
  • [Sm, bis] -, Consistency and related metamathematical properties, Report 75-02, Dept. of Math., Univ. of Amsterdam, 1975.
  • [S, W] Yoshindo Suzuki and George Wilmers, Non-standard models for set theory, The Proceedings of the Bertrand Russell Memorial Logic Conference (Uldum, 1971) Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 278–314. MR 0351814
  • [W] Alex Wilkie, On models of arithmetic–answers to two problems raised by H. Gaifman, J. Symbolic Logic 40 (1975), no. 1, 41–47. MR 0429547
  • [Wi] G. Wilmers, Thesis, Manchester, 1975.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03H15, 03F30

Retrieve articles in all journals with MSC: 03H15, 03F30

Additional Information

Article copyright: © Copyright 1978 American Mathematical Society