Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T20:07:19.362Z Has data issue: false hasContentIssue false
  • English
  • Français

GENERALIZATIONS OF GÖDEL’S INCOMPLETENESS THEOREMS FOR ∑n-DEFINABLE THEORIES OF ARITHMETIC

Published online by Cambridge University Press:  07 November 2017

MAKOTO KIKUCHI  and
TAISHI KURAHASHI
MAKOTO KIKUCHI*
Affiliation:
Graduate School of System Informatics, Kobe University
TAISHI KURAHASHI*
Affiliation:
Department of Natural Science, National Institute of Technology Kisarazu College
*
*GRADUATE SCHOOL OF SYSTEM INFORMATICS KOBE UNIVERSITY 1-1 ROKKODAI, NADA, KOBE 657-8501, JAPAN E-mail: [email protected]
†DEPARTMENT OF NATURAL SCIENCE NATIONAL INSTITUTE OF TECHNOLOGY, KISARAZU COLLEGE 2-11-1 KIYOMIDAI-HIGASHI, KISARAZU, CHIBA 292-0041, JAPAN E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It is well known that Gödel’s incompleteness theorems hold for ∑1-definable theories containing Peano arithmetic. We generalize Gödel’s incompleteness theorems for arithmetically definable theories. First, we prove that every ∑n+1-definable ∑n-sound theory is incomplete. Secondly, we generalize and improve Jeroslow and Hájek’s results. That is, we prove that every consistent theory having ∏n+1 set of theorems has a true but unprovable ∏n sentence. Lastly, we prove that no ∑n+1-definable ∑n -sound theory can prove its own ∑n-soundness. These three results are generalizations of Rosser’s improvement of the first incompleteness theorem, Gödel’s first incompleteness theorem, and the second incompleteness theorem, respectively.

Keywords

03F3003F40Gödel’s incompleteness theorems∑n-definable theories
Type
Research Article
Information
The Review of Symbolic Logic , Volume 10 , Issue 4 , December 2017 , pp. 603 - 616
Copyright
Copyright © Association for Symbolic Logic 2017 

References

BIBLIOGRAPHY

Beklemishev, L. D. (2005). Reflection principles and provability algebras in formal arithmetic. Russian Mathematical Surveys, 60(2), 197–268.CrossRefGoogle Scholar
Feferman, S. (1960). Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae, 49, 35–92.CrossRefGoogle Scholar
Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. (in German). Monatshefte für Mathematik und Physik, 38(1), 173–198. English translation in Kurt Gödel, Collected Works, Vol. 1. pp. 145–195.CrossRefGoogle Scholar
Grzegorczyk, A., Mostowski, A., & Ryll-Nardzewski, C. (1958). The classical and the ω-complete arithmetic. The Journal of Symbolic Logic, 23(2), 188–206.Google Scholar
Hájek, P. (1977). Experimental logics and ${\rm{\Pi }}_3^0$ theories. The Journal of Symbolic Logic, 42(4), 515–522.CrossRefGoogle Scholar
Isaacson, D. (2011). Necessary and sufficient conditions for undecidability of the Gödel sentence and its truth. In DeVidi, D., Hallett, M., and Clark, P., editors. Logic, Mathematics, Philosophy: Vintage Enthusiasms. Essays in Honour of John L. Bell. The Western Ontario Series in Philosophy of Science, Vol. 75. Dordrecht: Springer, pp. 135–152.Google Scholar
Jeroslow, R. G. (1975). Experimental logics and ${\rm{\Delta }}_2^0$ -theories. Journal of Philosophical Logic, 4(3), 253–267.Google Scholar
Kaså, M. (2012). Experimental logics, mechanism and knowable consistency. Theoria, 78(3), 213–224.Google Scholar
Kaye, R. (1991). Models of Peano Arithmetic. Oxford Logic Guides, Vol. 15. New York: Oxford Science Publications.Google Scholar
Kreisel, G. (1957). A refinement of ω-consistency (abstract). The Journal of Symbolic Logic, 22, 108–109.Google Scholar
Kreisel, G. & Lévy, A. (1968). Reflection principles and their use for establishing the complexity of axiomatic systems. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 14, 97–142.Google Scholar
Lindström, P. (1997). Aspects of Incompleteness. Lecture Notes in Logic, Vol. 10. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Mostowski, A. (1952). On models of axiomatic systems. Fundamenta Mathematicae, 39, 133–158.CrossRefGoogle Scholar
Niebergall, K.-G. (2005). “Natural” representations and extensions of Gödel’s second theorem. In Baaz, M., Friedman, S.-D., and K., J., editors. Logic Colloquium ’01. Urbana, IL, and Wellesley, MA: Association for Symbolic Logic/A K Peters, pp. 350–368.CrossRefGoogle Scholar
Rosser, J. B. (1936). Extensions of some theorems of Gödel and Church. The Journal of Symbolic Logic, 1(3), 87–91.Google Scholar
Rosser, J. B. (1937). Gödel theorems for nonconstructive logics. The Journal of Symbolic Logic, 2(3), 129–137.Google Scholar
Smoryński, C. (1977a). The incompleteness theorems. In Barwise, J., editor. Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics, Vol. 90. Amsterdam: North-Holland Publishing, pp. 821–865.Google Scholar
Smoryński, C. (1977b). ω-consistency and reflection. In Colloque International de Logique: Clermont-Ferrand, 18–25 juillet 1975. Paris: Editions du C.N.R.S., pp. 167–181.Google Scholar
Smoryński, C. (1985). Self-reference and Modal Logic. Universitext. New York: Springer-Verlag.Google Scholar