Mathematical Logic Joseph R Shoenfield Pdf

Request Permissions

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

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 https://doi.org/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) Springer, Berlin, 1973, pp. 113–170. Lecture Notes in Math., Vol. 337. MR 0376310
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
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 https://doi.org/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
Joram Hirschfeld and William H. Wheeler, Forcing, arithmetic, division rings, Lecture Notes in Mathematics, Vol. 454, Springer-Verlag, Berlin-New York, 1975. MR 0389581
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 https://doi.org/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 https://doi.org/10.1016/0003-4843%2873%2990015-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 https://doi.org/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 https://doi.org/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 ${\rm 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.2307/2272974
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

---, 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 https://doi.org/10.2307/2272268

G. Wilmers, Thesis, Manchester, 1975.

J. Barwise, Infinitary methods in the model theory of set theory, Logic Colloquium '69, North-Holland, Amsterdam, 1971, pp. 53-66. MR 43 #3103.

S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960/61), 35-92. MR 26 #4913.

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.

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.

---, Uniform extension operators for models and their applications, Sets, Models and Recursion Theory, North-Holland, Amsterdam, 1967, pp. 122-155. MR 36 #3640.

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.

D. C. Goldrei, A. Macintyre and H. Simmons, The forcing companions of number theories, Israel J. Math. 14 (1973), 317-337. MR 48 #5853.

D. Hilbert and P. Bernays, Grundlagen der Mathematik. II, Springer, Berlin, 1939.

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.

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.

J. L. Krivine and K. McAloon, Forcing and generalized quantifiers, Ann. Math. Logic 5 (1973), 199-255.

---, Some true unprovable formulas for set theory, Proc. Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 332-341. MR 50 #9580.

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.

G. Kreisel and H. Wang, Some applications of formalized consistency proofs, Fund. Math. 42 (1955), 101-110. MR 17, 447.

L. Manewitz, Internal end-extensions of Peono arithmetic and a problem of Gaifman, J. London Math. Soc. 13 (1976), 80-82.

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.

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.

---, Formules de Rosser pour ZF, C. R. Acad. Sci. Paris Sér. A-B 281 (1975), no. 16, Ai, A669-A672. MR 52 #5417.

---, 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, Pergamon, Oxford; PWN, Warsaw, 1961, pp. 257-263. MR 27 #2425.

A. Macintyre and H. Simmons, Algebraic properties of number theories, Israel J. Math. 22 (1975), 7-27.

R. Montague, Semantical closure and non-finite axiomatizability. I, Infinitistic Methods, Pergamon, Oxford; PWN, Warsaw, 1961, pp. 45-69. MR 27 #38.

A. Mostowski, On models of axiomatic systems, Fund. Math. 39 (1952), 133-158. (1953) MR 14, 938.

---, A generalization of the incompleteness theorem, Fund. Math. 49 (1960/61), 205-232. MR 24 # A41.

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.

H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61.

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 14, 938.

J. R. Shoenfield, Mathematical logic, Addison-Wesley, Reading, Mass., 1967. MR 37 #1224.

D. Scott, On constructing models for arithmetic, Infinitistic Methods, Pergamon, Oxford; PWN, Warsaw, 1961, pp. 235-255. MR 27 #2423.

H. Simmons, Existentially closed structures, J. Symbolic Logic 37 (1972), 293-310. MR 51 #12518.

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.

---, Consistency and related metamathematical properties, Report 75-02, Dept. of Math., Univ. of Amsterdam, 1975.

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.

A. Wilkie, On models of arithmetic-Answers to two questions raised by H. Gaifman, J. Symbolic Logic 40 (1973), 41-47.

G. Wilmers, Thesis, Manchester, 1975.