×

Generalizations of Gödel’s incompleteness theorems for \(\Sigma_n\)-definable theories of arithmetic. (English) Zbl 1426.03038

The paper consists of six sections. The main technical contributions are in Sections 4 and 5 (Section 1 is the introduction, Section 2 contains preliminaries, Section 3 is on “Notions related to consistency and completeness” and Section 6 is titled “Acknowledgements”). The authors already note in footnote 2 of Section 1 that (as informed by the referee) the paper has overlap with the [the reviewer and P. Seraji, “Gödel-Rosser’s incompleteness theorems for non-recursively enumerable theories”, Preprint, arXiv:1506.02790] and [the reviewer and P. Seraji, J. Log. Comput. 27, No. 5, 1391–1397 (2017; Zbl 1444.03166)].
In Section 4, “The first incompleteness theorem”, the two new results that do not already appear in [the reviewer and Seraji, Preprint, loc. cit.; (2017), loc. cit.)] is Corollary 4.6 (the existence of two non-equivalent \(\Sigma_{n+1}\) definitions for any \(\Sigma_{n+1}\)-definable theory) and Theorem 4.12 (the \(\Pi_n\)-incompleteness of any consistent theory whose set of theorems is \(\Pi_{n+1}\)-definable); the latter result improves some results of R. G. Jeroslow [J. Philos. Log. 4, 253–267 (1975; Zbl 0319.02024)] and P. Hajek [J. Symb. Log. 42, 515–522 (1978; Zbl 0428.03043)], and answers negatively a problem of Hájek [loc. cit.] which asked for the existence of a \(\Pi_2\)-complete and consistent theory whose set of theorems is \(\Pi_3\)-definable.
Section 5, “The second incompleteness theorem”, has also some overlap with the preprint [P. Seraji and C. Chao, “Gödel’s second incompleteness theorem for definable theories”, Preprint, arXiv:1602.02416] and the article [C. Chao and P. Seraji, “Gödel’s second incompleteness theorem for \(\Sigma_n\)-definable theories”, Log. J. IGPL 26, No. 2, 255–257 (2018; doi:10.1093/jigpal/jzx061)] which is not mentioned in the paper under review (the authors may not have known about these).
One of the new results of the paper under review that is not in [Seraji and Chao, Preprint, loc. cit.; (2018), loc. cit.)] is Theorem 5.13 which states the existence of a \(\Sigma_{n+1}\) definition \(\sigma\) of any \(\Sigma_n\)-sound and \(\Pi_n\)-definable theory \(T\) such that \({\mathtt Con}_\sigma\) is independent from \(T\).
One feature of the generalized incompleteness results that is not studied in the paper under review but has been investigated in the aforementioned papers [the reviewer and Seraji, Preprint, loc. cit.; (2017), loc. cit.); Seraji and Chao, Preprint, loc. cit.; (2018), loc. cit.)] is the optimality of the results. For example, Theorems 4.8 and 4.9 which state that if a \(\Sigma_{n+1}\)-definable theory \(T\) is either \(\Sigma_n\)-sound or \(\Sigma_n\)-consistent, then \(T\) is incomplete (with an undecidable \(\Pi_{n+1}\)-sentence) are both optimal, since there exist some complete, \(\Sigma_{n+1}\)-definable and \(\Sigma_n\)-sound (thus \(\Sigma_n\)-consistent) theories; proved in [the reviewer and Seraji, (2017), loc. cit.)]. Also, Theorem 5.6, which states the unprovability of \(\Sigma_n\)-soundness of \(T\) in \(T\), when \(T\) is a \(\Sigma_{n+1}\)-definable and \(\Sigma_n\)-sound theory, is optimal, since some \(\Sigma_{n+1}\)-definable and \(\Sigma_{n-1}\)-sound theories can prove their own \(\Sigma_{n-1}\)-soundness; proved in [Seraji and Chao, (2018), loc. cit.)].

MSC:

03F30 First-order arithmetic and fragments
03F40 Gödel numberings and issues of incompleteness
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] BeklemishevL. D. (2005). Reflection principles and provability algebras in formal arithmetic. Russian Mathematical Surveys, 60(2), 197-268.10.1070/RM2005v060n02ABEH000823 · Zbl 1097.03054 · doi:10.1070/RM2005v060n02ABEH000823
[2] FefermanS. (1960). Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae, 49, 35-92.10.4064/fm-49-1-35-92 · Zbl 0095.24301 · doi:10.4064/fm-49-1-35-92
[3] GödelK. (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. · JFM 57.0054.02
[4] GrzegorczykA., MostowskiA., & Ryll-NardzewskiC. (1958). The classical and the ω-complete arithmetic. The Journal of Symbolic Logic, 23(2), 188-206.10.2307/2964398 · Zbl 0084.24801 · doi:10.2307/2964398
[5] HájekP. (1977). Experimental logics and <![CDATA \([{\rm{\Pi }}_3^0]]\)> theories. The Journal of Symbolic Logic, 42(4), 515-522.10.2307/2271872 · Zbl 0428.03043 · doi:10.2307/2271872
[6] IsaacsonD. (2011). Necessary and sufficient conditions for undecidability of the Gödel sentence and its truth. In DeVidiD., HallettM., and ClarkP., 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. · Zbl 1259.03075
[7] JeroslowR. G. (1975). Experimental logics and <![CDATA \([{\rm{\Delta }}_2^0]]\)>-theories. Journal of Philosophical Logic, 4(3), 253-267.10.1007/BF00262039 · Zbl 0319.02024 · doi:10.1007/BF00262039
[8] KasåM. (2012). Experimental logics, mechanism and knowable consistency. Theoria, 78(3), 213-224.10.1111/j.1755-2567.2012.01133.x · doi:10.1111/j.1755-2567.2012.01133.x
[9] KayeR. (1991). Models of Peano Arithmetic. Oxford Logic Guides, Vol. 15. New York: Oxford Science Publications. · Zbl 0744.03037
[10] KreiselG. (1957). A refinement of ω-consistency (abstract). The Journal of Symbolic Logic, 22, 108-109.
[11] KreiselG. & LévyA. (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.10.1002/malq.19680140702 · Zbl 0167.01302 · doi:10.1002/malq.19680140702
[12] LindströmP. (1997). Aspects of Incompleteness. Lecture Notes in Logic, Vol. 10. Berlin: Springer-Verlag. · Zbl 0882.03054
[13] MostowskiA. (1952). On models of axiomatic systems. Fundamenta Mathematicae, 39, 133-158.10.4064/fm-39-1-133-158 · Zbl 0053.20102 · doi:10.4064/fm-39-1-133-158
[14] NiebergallK.-G. (2005). “Natural” representations and extensions of Gödel’s second theorem. In BaazM., FriedmanS.-D., and K.J., editors. Logic Colloquium ’01. Urbana, IL, and Wellesley, MA: Association for Symbolic Logic/A K Peters, pp. 350-368. · Zbl 1081.03058
[15] RosserJ. B. (1936). Extensions of some theorems of Gödel and Church. The Journal of Symbolic Logic, 1(3), 87-91.10.2307/2269028 · Zbl 0015.33802 · doi:10.2307/2269028
[16] RosserJ. B. (1937). Gödel theorems for nonconstructive logics. The Journal of Symbolic Logic, 2(3), 129-137.10.2307/2266293 · JFM 63.0824.02 · doi:10.2307/2266293
[17] SmoryńskiC. (1977a). The incompleteness theorems. In BarwiseJ., editor. Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics, Vol. 90. Amsterdam: North-Holland Publishing, pp. 821-865.10.1016/S0049-237X(08)71123-6
[18] SmoryńskiC. (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. · Zbl 0436.03050
[19] SmoryńskiC. (1985). Self-reference and Modal Logic. Universitext. New York: Springer-Verlag. · Zbl 0596.03001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.