Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Completeness theorems, incompleteness theorems and models of arithmetic
HTML articles powered by AMS MathViewer

by Kenneth McAloon PDF
Trans. Amer. Math. Soc. 239 (1978), 253-277 Request permission

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
  • 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
  • S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960/61), 35–92. MR 147397, DOI 10.4064/fm-49-1-35-92
  • Harvey Friedman, Some applications of Kleene’s methods for intuitionistic systems, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Lecture Notes in Math., Vol. 337, Springer, Berlin, 1973, pp. 113–170. MR 0376310
  • Haim Gaifman, A note on models and submodels of arithmetic, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Lecture Notes in Math., Vol. 255, Springer, Berlin, 1972, pp. 128–144. MR 0419215
  • 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
  • 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 159747
  • D. C. Goldrei, A. Macintyre, and H. Simmons, The forcing companions of number theories, Israel J. Math. 14 (1973), 317–337. MR 327511, DOI 10.1007/BF02764894
  • D. Hilbert and P. Bernays, Grundlagen der Mathematik. II, Die Grundlehren der mathematischen Wissenschaften, Band 50, Springer-Verlag, Berlin-New York, 1970 (German). Zweite Auflage. MR 0272596, DOI 10.1007/978-3-642-86896-2
  • Joram Hirschfeld and William H. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Mathematics, Vol. 454, Springer-Verlag, Berlin-New York, 1975. MR 0389581, DOI 10.1007/BFb0064082
  • 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 228333, DOI 10.1002/malq.19680140702
  • Jean-Louis Krivine and Kenneth McAloon, Forcing and generalized quantifiers, Ann. Math. Logic 5 (1972/73), 199–255. MR 446890, DOI 10.1016/0003-4843(73)90015-6
  • 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
  • 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 384497
  • G. Kreisel and Hao Wang, Some applications of formalized consistency proofs, Fund. Math. 42 (1955), 101–110. MR 73539, DOI 10.4064/fm-42-1-101-110
  • 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 441722, DOI 10.1112/jlms/s2-13.1.80
  • 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.
  • 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 369059
  • Kenneth McAloon, Formules de Rosser pour $\textrm {ZF}$, C. R. Acad. Sci. Paris Sér. A-B 281 (1975), no. 16, Ai, A669–A672 (French, with English summary). MR 384543
  • —, Consistency statements and number theories, Proc. 1975 Logic Colloq. at Clermont-Ferrand (M. Guillaume, Editor), Publ. C.N.R.S., 1977.
  • 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
  • A. Macintyre and H. Simmons, Algebraic properties of number theories, Israel J. Math. 22 (1975), no. 1, 7–27. MR 398820, DOI 10.1007/BF02757270
  • R. Montague, Semantical closure and non-finite axiomatizability. I, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 45–69. MR 0150033
  • A. Mostowski, On models of axiomatic systems, Fund. Math. 39 (1952), 133–158 (1953). MR 54547, DOI 10.4064/fm-39-1-133-158
  • A. Mostowski, A generalization of the incompleteness theorem, Fund. Math. 49 (1960/61), 205–232. MR 130174, DOI 10.4064/fm-49-2-205-232
  • 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
  • Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
  • J. B. Rosser, Extensions of some theorems of Gödel and Church, J. Symbolic Logic 1 (1936), 89-91.
  • C. Ryll-Nardzewski, The role of the axiom of induction in elementary arithmetic, Fund. Math. 39 (1952), 239–263 (1953). MR 54546, DOI 10.4064/fm-39-1-239-263
  • Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
  • 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
  • H. Simmons, Existentially closed structures, J. Symbolic Logic 37 (1972), 293–310. MR 376342, DOI 10.2307/2272974
  • C. A. Smoryński, Applications of Kripke models, Metamathematical investigation of intuitionistic arithmetic and analysis, Lecture Notes in Mathematics, Vol. 344, Springer, Berlin, 1973, pp. 324–391. MR 0444442
  • —, Consistency and related metamathematical properties, Report 75-02, Dept. of Math., Univ. of Amsterdam, 1975.
  • 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
  • Alex Wilkie, On models of arithmetic–answers to two problems raised by H. Gaifman, J. Symbolic Logic 40 (1975), no. 1, 41–47. MR 429547, DOI 10.2307/2272268
  • 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
  • © Copyright 1978 American Mathematical Society
  • 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