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
DOI: https://doi.org/10.1090/S0002-9947-1978-0487048-9
MathSciNet review: 487048
Full-text PDF

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] J. Barwise, Infinitary methods in the model theory of set theory, Logic Colloquium '69, North-Holland, Amsterdam, 1971, pp. 53-66. MR 43 #3103. MR 0277370 (43:3103)
  • [Fef] S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960/61), 35-92. MR 26 #4913. MR 0147397 (26:4913)
  • [Fr] H. Friedman, Some applications of Kleene's methods for intuitionistic systems, Cambridge Summer School in Mathematical Logic, Lecture Notes in Math., vol. 337, Springer-Verlag, Berlin and New York, 1973, pp. 113-170. MR 51 # 12486. MR 0376310 (51:12486)
  • [G] H. Gaifman, A note on models and submodels of arithmetic, Conf. in Math. Logic -- London '70, Lecture Notes in Math., vol. 255, Springer-Verlag, Berlin and New York, 1972, pp. 128-144. MR 0419215 (54:7247)
  • [G, bis] -, Uniform extension operators for models and their applications, Sets, Models and Recursion Theory, North-Holland, Amsterdam, 1967, pp. 122-155. MR 36 #3640. MR 0220586 (36:3640)
  • [G, K, T] R. Gandy, G. Kreisel and W. Tait, Set existence, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 577-582. MR 28 #2964a. MR 0159747 (28:2964a)
  • [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 48 #5853. MR 0327511 (48:5853)
  • [H, B] D. Hilbert and P. Bernays, Grundlagen der Mathematik. II, Springer, Berlin, 1939. MR 0272596 (42:7477)
  • [H, W] J. Hirschfeld and W. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Math., vol. 454, Springer-Verlag, Berlin and New York, 1975. MR 52 # 10412. MR 0389581 (52:10412)
  • [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 37 #3914. MR 0228333 (37:3914)
  • [K, M] J. L. Krivine and K. McAloon, Forcing and generalized quantifiers, Ann. Math. Logic 5 (1973), 199-255. MR 0446890 (56:5209a)
  • [K, M, bis] -, Some true unprovable formulas for set theory, Proc. Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 332-341. MR 50 #9580. MR 0357112 (50:9580)
  • [K, T] G. Kreisel and G. Takeuti, Formally self-referential propositions for cut free classical analysis and related systems, Dissertations Math. (Rozprawy Mat.) 118 (1974), 55 pp. MR 52 #5374. MR 0384497 (52:5374)
  • [K, W] G. Kreisel and H. Wang, Some applications of formalized consistency proofs, Fund. Math. 42 (1955), 101-110. MR 17, 447. MR 0073539 (17:447g)
  • [Man] L. Manewitz, Internal end-extensions of Peono arithmetic and a problem of Gaifman, J. London Math. Soc. 13 (1976), 80-82. MR 0441722 (56:120)
  • [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] K. 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. MR 51 #5295. MR 0369059 (51:5295)
  • [Mc, bis] -, Formules de Rosser pour ZF, C. R. Acad. Sci. Paris Sér. A-B 281 (1975), no. 16, Ai, A669-A672. MR 52 #5417. MR 0384543 (52:5417)
  • [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, Pergamon, Oxford; PWN, Warsaw, 1961, pp. 257-263. MR 27 #2425. MR 0152447 (27:2425)
  • [M, S] A. Macintyre and H. Simmons, Algebraic properties of number theories, Israel J. Math. 22 (1975), 7-27. MR 0398820 (53:2671)
  • [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] M. Rabin, Non-standard models and independence of the induction axiom, Essays on the foundations of mathematics, Magnes Press, Hebrew Univ., Jerusalem, 1961, pp. 287-299. MR 28 #4999. MR 0161795 (28:4999)
  • [Rog] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [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 14, 938. MR 0054546 (14:938b)
  • [Sch] J. R. Shoenfield, Mathematical logic, Addison-Wesley, Reading, Mass., 1967. MR 37 #1224. MR 0225631 (37:1224)
  • [Sco] D. Scott, On constructing models for arithmetic, Infinitistic Methods, Pergamon, Oxford; PWN, Warsaw, 1961, pp. 235-255. MR 27 #2423. MR 0152445 (27:2423)
  • [Sim] H. Simmons, Existentially closed structures, J. Symbolic Logic 37 (1972), 293-310. MR 51 #12518. MR 0376342 (51:12518)
  • [Sm] C. Smorynski, Applications of Kripke models, Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Lecture Notes in Math., vol. 344, Springer-Verlag, Berlin and New York, 1973. MR 0444442 (56:2795)
  • [Sm, bis] -, Consistency and related metamathematical properties, Report 75-02, Dept. of Math., Univ. of Amsterdam, 1975.
  • [S, W] Y. Suzuki and G. Wilmers, Non-standard models for set theory, Proc. Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 278-314. MR 50 #4302. MR 0351814 (50:4302)
  • [W] A. Wilkie, On models of arithmetic-Answers to two questions raised by H. Gaifman, J. Symbolic Logic 40 (1973), 41-47. MR 0429547 (55:2560)
  • [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

DOI: https://doi.org/10.1090/S0002-9947-1978-0487048-9
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society