×

Current research on Gödel’s incompleteness theorems. (English) Zbl 1497.03067

This is “a comprehensive survey paper for the current state-of-art” in the researches on Gödel’s first and second incompleteness theorems, that the author felt “is missing from the literature. […] The motivation of this paper is four-fold:
Give the reader an overview of the current state-of-art of research on incompleteness.
Classify these new advances on incompleteness under some important themes.
Propose some new questions not covered in the literature.
Set the direction for the future research of incompleteness.

[…] Due to space limitations and our personal taste, it is impossible to cover all research results from the literature related to incompleteness in this survey. Therefore, we will focus on three aspects of new advances in research on incompleteness:
classifications of different proofs of Gödel’s incompleteness theorems;
the limit of the applicability of G1 [Gödel’s first incompleteness theorem];
the limit of the applicability of G2 [Gödel’s second incompleteness theorem].

[…] An important and interesting topic concerning incompleteness is missing in this paper: philosophy of Gödel’s incompleteness theorems. For us, the widely discussed and most important philosophical questions about Gödel’s incompleteness theorems are: the relationship between G1 and the mechanism thesis, the status of Gödel’s disjunctive thesis, and the intensionality problem of G2. We leave a survey of philosophical discussions of Gödel’s incompleteness theorems for a future philosophy paper.”
It should be noted that the research on the field surveyed in this expository article is live and very active. The author classified “different proofs of Gödel’s incompleteness theorems […] using the following criteria:
proof-theoretic proof;
recursion-theoretic proof;
model-theoretic proof;
proof via arithmetization;
proof via the Diagnolisation Lemma;
proof based on ‘logical paradox’;
constructive proof;
proof having the Rosser property;
the independent sentence has natural and real mathematical content.

[…] However, these aspects are not exclusive: a proof of G1 or G2 may satisfy several of the above criteria.”
The reader should be warned about the following minor errors:
(p. 132): The Kolmogorov complexity of a number \(n\) is the size of {\em the shortest} programs which generates \(n\) (not “the size of a program which generates \(n\)”).
(p. 139): The notion of a homogeneous set is not defined in the paper.
(p. 142): \(\Gamma^d\), where \(\Gamma\) denotes either \(\Sigma_n^0\) or \(\Pi_n^0\) for some \(n\geq 1\), is the {\em dual} of \(\Gamma\); so if \(\Gamma=\Sigma_n^0\) then \(\Gamma^d=\Pi_n^0\), and if \(\Gamma=\Pi_n^0\) then \(\Gamma^d=\Sigma_n^0\).
(p. 142): No reference is given for Fact 4.3, or for Solovay’s result before that.
(p. 147): “Up to now” means {\em until that stage in the paper} (and not in the state-of-art of the results); as the author mentions E. Jeřábek’s results afterwards (though without citing the reference [J. Math. Log. 20, No. 1, Article ID 2050002, 52 p. (2020; Zbl 1484.03126)]).
(p. 162): In reference [31] the name H. B. Enderton should be R. L. Epstein.
This interesting paper contains some exciting open problems scattered throughout the text:
(p. 130): “As far as we know, at present there is no convincing essentially self-reference-free proofs of either G2 or of Tarski’s Theorem of the Undefinability of Truth.”
(p. 138): “An interesting open question is: whether there is a standard proof predicate [like \(\mathbf{Prf}_T(u,v)\) expressing that ‘\(v\) is a \(T\)-proof of \(u\)’] such that \(Y^R(\overline{n})\) and \(Y^R(\overline{n+1})\) are not provably equivalent for some \(n\in\mathbb{N}\)”, where \(Y^R(x)\) is a Rosser-type Yablo formula of \(\mathbf{Prf}_T\), i.e., \(\mathbf{PA}\vdash\forall x \big[Y^R(x)\leftrightarrow \forall y>x\neg\mathbf{Pr}_T^R(\ulcorner Y^R(\dot{y})\urcorner)\big]\) in which \(\mathbf{Pr}_T^R(x)=\exists y[\mathbf{Prf}_T(x,y)\wedge\forall z\leq y\neg\mathbf{Prf}_T(\dot{\neg}x,z)]\).
(p. 147): Let \(\lhd\) denote strict interpretability (\(S\lhd T\) iff “\(T\) interprets \(S\), but \(S\) does not interpret \(T\)”) and \(\mathsf{ D}\) be the set of theories for which \(\mathsf{G1}\) holds and are strictly interpretable in Robinson’s arithmetic \(\mathbf{R}\).
“Question 4.15.
Is \(\langle\mathsf{D},\lhd\rangle\) well-founded?
Are any two elements of \(\langle\mathsf{D},\lhd\rangle\) comparable?
Does there exist a minimal theory w.r.t. interpretation such that \(\mathsf{G1}\) holds for it?”

(p. 155): “[C]haracterizing the consistency of infinitely axiomatized r.e. theories is […] a big open problem”.
(p. 159): “[T]he exact axiomatization of the provability logic \(\mathbf{PL}_\pi(T)\) under Feferman’s numeration \(\pi(x)\) is not known.”
I wholeheartedly recommend studying this survey to all logicians and philosophers.

MSC:

03F40 Gödel numberings and issues of incompleteness
03F30 First-order arithmetic and fragments
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

Citations:

Zbl 1484.03126
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamowicz, Z. and Bigorajska, T., Existentially closed structures and Gödel’s second incompleteness theorem. The Journal of Symbolic Logic, vol. 66 (2001), no. 1, pp. 349-356. · Zbl 0981.03043
[2] Arai, T., Derivability conditions on Rosser’s provability predicates. Notre Dame Journal of Formal Logic, vol. 31 (1990), no. 4, pp. 487-497. · Zbl 0722.03041
[3] Artemov, S. N., The provability of consistency, preprint, 2019, arXiv:1902.07404v5.
[4] Avigad, J., Incompleteness via the halting problem, 2005, https://www.andrew.cmu.edu/user/avigad/Teaching/halting.pdf.
[5] Barwise, K. J., Comments introducing Boolos’ article. Notices of the American Mathematical Society, vol. 36 (1989), no. 388.
[6] Beklemishev, L. D., On the classification of propositional provability logics. Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya, vol. 53 (1989), no. 5, pp. 915-943, translated in Mathematics of the USSR-Izvestiya, vol. 35 (1990), no. 2, pp. 247-275. · Zbl 0704.03005
[7] Beklemishev, L. D., The Worm Principle, Logic Group Preprint Series, vol. 219, Utrecht University, the Netherlands, 2003. · Zbl 1108.03055
[8] Beklemishev, L. D., Gödel incompleteness theorems and the limits of their applicability I. Russian Mathematical Surveys, vol. 65 (2010), no. 5, pp. 857-899. · Zbl 1213.03071
[9] Beklemishev, L. D. and Shamkanov, D. S., Some abstract versions of Gödel’s second incompleteness theorem based on non-classical logics, A Tribute to Albert Visser (Alberti, L. A., editor), College Publications, 2016, pp. 15-29. · Zbl 1418.03175
[10] Berline, C., Mcaloon, K., and Ressayre, J. P. (eds.), Model Theory and Arithmetic, Lecture Notes in Mathematics, vol. 890, Springer, Berlin, 1981. · Zbl 0465.00004
[11] Bezboruah, A. and Shepherdson, J. C., Gödel’s second incompleteness theorem for \(\boldsymbol{Q} \). The Journal of Symbolic Logic, vol. 41 (1976), no. 2, pp. 503-512. · Zbl 0328.02017
[12] Blanck, R., Contributions to the Metamathematics of Arithmetic: Fixed Points, Independence, and Flexibility, Ph.D. thesis, University of Gothenburg, Acta Universitatis Gothoburgensis, 2017.
[13] Boolos, G., A new proof of the Gödel incompleteness theorem. Notices of the American Mathematical Society, vol. 36 (1989), pp. 388-390. · Zbl 0972.03544
[14] Boolos, G., The Logic of Provability, Cambridge University Press, Cambridge, 1995. · Zbl 0891.03004
[15] Bovykin, A., Brief introduction to unprovability. Logic Colloquium, Lecture Notes in Logic, vol. 32, Cambridge University Press, Cambridge, 2009, pp 38-64. · Zbl 1187.03049
[16] Buldt, B., The scope of Gödel’s first incompleteness theorem. Logica Universalis, vol. 8 (2014), no. (3-4), pp. 499-552. · Zbl 1339.03004
[17] Buss, S. R., Bounded Arithmetic, Studies in Proof Theory, Lecture Notes, vol. 3, Bibliopolis, Naples, 1986. · Zbl 0649.03042
[18] Buss, S. R., First-order theory of arithmetic. Handbook Proof Theory, Elsevier, Amsterdam, 1998, pp 79-148. · Zbl 0911.03029
[19] Chaitin, G. J., Information-theoretic limitations of formal systems. Journal of the Association for Computing Machinery, vol. 21 (1974), pp. 403-424. · Zbl 0287.68027
[20] Chao, C. and Seraji, P., Gödel’s second incompleteness theorem for \({\varSigma}_n\) -definable theories. Logic Journal of the IGPL, vol. 26 (2018), no. 2, pp. 255-257. · Zbl 1492.03019
[21] Cheng, Y., Incompleteness for Higher-Order Arithmetic: An Example Based on Harrington’s Principle, Springer Series: Springer, Briefs in Mathematics, Springer, 2019. · Zbl 1457.03002
[22] Cheng, Y., Finding the limit of incompleteness I, this Journal, 2020, to appear, doi:10.1017/bsl.2020.09. · Zbl 1464.03089
[23] Cheng, Y., On the depth of Gödel’s incompleteness theorem, preprint, 2020, arXiv:2008.13142.
[24] Cheng, Y. and Schindler, R., Harrington’s principle in higher order arithmetic. The Journal of Symbolic Logic, vol. 80, (2015), no. 02, pp 477-489. · Zbl 1373.03093
[25] Cieśliński, C., Heterologicality and incompleteness. Mathematical Logic Quarterly, vol. 48 (2002), no. 1, pp. 105-110. · Zbl 0990.03028
[26] Cieśliński, C. and Urbaniak, R., Gödelizing the Yablo sequence. Journal of Philosophical Logic, vol. 42 (2013), no. (5), pp. 679-695. · Zbl 1288.03033
[27] Clote, P. and Mcaloon, K., Two further combinatorial theorems equivalent to the 1-consistency of Peano arithmetic. Journal of Symbolic Logic, vol. 48 (1983), no.4, pp. 1090-1104. · Zbl 0545.03033
[28] Dean, W., Incompleteness via paradox and completeness. Review of Symbolic Logic, vol. 13 (2020), no. 3, pp. 541-592. · Zbl 1485.03244
[29] Enderton, H. B., A Mathematical Introduction to Logic, second ed.,Academic Press, Boston, MA, 2001. · Zbl 0992.03001
[30] Enderton, H. B., Computability Theory, An Introduction to Recursion Theory, Academic Press, Cambridge, MA, 2011. · Zbl 1243.03057
[31] Enderton, H. B. (with contributions by Szczerba, L. W.), Classical Mathematical Logic: The Semantic Foundations of Logic, Princeton University Press, 2011.
[32] Feferman, S., Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae, vol. 49 (1960), pp. 35-92. · Zbl 0095.24301
[33] Feferman, S., Transfinite recursive progressions of axiomatic theories. Journal of Symbolic Logic, vol. 27 (1962), pp. 259-316. · Zbl 0117.25402
[34] Feferman, S., The impact of the incompleteness theorems on mathematics. Notices of the AMS, vol. 53 (2006), no. 4, pp. 434-439. · Zbl 1100.03004
[35] Ferreira, F. and Ferreira, G., Interpretability in Robinson’s Q. this Journal, vol. 19 (2013), no. 3, pp. 289-317. · Zbl 1325.03072
[36] Fitch, F. B., A Gödelized formulation of the prediction paradox. American Philosophical Quarterly, vol. 1 (1964), pp. 161-164.
[37] Franzen, T., Inexhaustibility: A Non-Exhaustive Treatment, Lecture Notes in Logic, vol. 16, Cambridge University Press, Cambridge, 2017. · Zbl 1094.03001
[38] Friedman, H., On the necessary use of abstract set theory. Advances in Mathematics, vol. 41 (1981), pp. 209-280. · Zbl 0483.03030
[39] Friedman, H., Finite functions and the necessary use of large cardinals. Annals of Mathematics, vol. 148 (1998), pp. 803-893. · Zbl 0941.03050
[40] Friedman, H., Boolean Relation Theory and Incompleteness, Manuscript, to appear.
[41] Friedman, S.-D., Rathjen, M., and Weiermann, A., Slow consistency. Annals of Pure and Applied Logic, vol. 164 (2013), no. 3, pp. 382-393. · Zbl 1263.03055
[42] Ganea, M., Arithmetic on semigroups. Journal of Symbolic Logic, vol. 74 (2009), no. 1, pp. 265-278. · Zbl 1160.03038
[43] Gödel, K., Über formal unentscheidbare sätze der Principia Mathematica und verwandter systeme I. Monatshefte für Mathematik und Physik, vol. 38 (1931), no. 1, pp. 173-198. · JFM 57.0054.02
[44] Gödel, K., Kurt Gödel’s Collected Works, vol. 1: Publications 1929-1936, Oxford University Press, New York, 1986, pp. 145-195.
[45] Gordeev, L. and Weiermann, A., Phase transitions of iterated Higman-style well-partial-orderings. Archive for Mathematical Logic, vol. 51 (2012), no. 1-2, pp. 127-161. · Zbl 1251.03076
[46] Grabmayr, B., On the invariance of Gödel’s second theorem with regard to numberings. The Review of Symbolic Logic, 2020, doi: 10.1017/S1755020320000192. · Zbl 1487.03070
[47] Grzegorczyk, A., Undecidability without arithmetization. Studia Logica, vol. 79 (2005), no. 2, pp. 163-230. · Zbl 1080.03004
[48] Grzegorczyk, A. and Zdanowski, K., Undecidability and concatenation, Andrzej Mostowski and Foundational Studies (Ehrenfeucht, A., Marek, V. W., and Srebrny, M., editors), IOS Press, Amsterdam, 2008, pp. 72-91. · Zbl 1150.03014
[49] Guaspari, D., Partially conservative extensions of arithmetic. Transactions of the American Mathematical Society, vol. 254 (1979), pp. 47-68. · Zbl 0417.03030
[50] Guaspari, D. and Solovay, R. M., Rosser sentences. Annals of Mathematical Logic, vol. 16 (1979), no. 1, pp. 81-99. · Zbl 0426.03062
[51] Hájek, P., Interpretability and fragments of arithmetic, Arithmetic, Proof Theory and Computational Complexity (Clote, P. and Krajícek, J., editors), Oxford Logic Guides, 23, Clarendon Press, Oxford, 1993, pp. 185-196. · Zbl 0791.03033
[52] Hájek, P. and Paris, J., Combinatorial principles concerning approximations of functions. Archive for Mathematical Logic, vol. 26 (1986), no. 1-2, pp. 13-28. · Zbl 0645.03057
[53] Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Perspectives in Logic, vol. 3, Cambridge University Press, Cambridge, 2017. · Zbl 1365.03008
[54] Halbach, V. and Visser, A., Self-reference in arithmetic I. Review of Symbolic Logic, vol. 7 (2014a), no. 4, pp. 671-691. · Zbl 1337.03008
[55] Halbach, V. and Visser, A., Self-reference in arithmetic II. Review of Symbolic Logic, vol. 7 (2014b), no. (4), pp. 692-712. · Zbl 1337.03009
[56] Hamano, M. and Okada, M., A relationship among Gentzen’s proof-reduction, Kirby-Paris’ hydra game, and Buchholz’s hydra game. Mathematical Logic Quarterly, vol. 43 (1997), no. 1, pp. 103-120. · Zbl 0872.03038
[57] Henk, P. and Pakhomov, F., Slow and ordinary provability for Peano arithmetic, preprint, 2016, arXiv:1602.1822.
[58] Higuchi, K. and Horihata, Y., Weak theories of concatenation and minimal essentially undecidable theories—An encounter of WTC and S2S. Archive for Mathematical Logic, vol. 53 (2014), no. 7-8, pp. 835-853. · Zbl 1339.03054
[59] Hilbert, D. and Bernays, P., Grundlagen der Mathematik, Vols. I and II, second ed.,Springer-Verlag, Berlin, 1934 and 1939. · JFM 60.0017.02
[60] Hilbert, D. and Bernays, P., Grundlagen der Mathematik, vol. II, Springer-Verlag, Berlin, 1939. · Zbl 0020.19301
[61] Isaacson, D., Arithmetical truth and hidden higher-order concepts, Logic Colloquium 85 (Barwise, J., Kaplan, D., Keisler, H. J., Suppes, P., and Troelstra, A. S., editors), Studies in Logic and the Foundations of Mathematics, vol. 122, North-Holland, Amsterdam, 1987, pp. 147-169. · Zbl 0628.03002
[62] Isaacson, D., Necessary and sufficient conditions for undecidability of the Gödel sentence and its truth, Logic, Mathematics, Philosophy: Vintage Enthusiasms (Devidi, D., Hallett, M., and Clark, P., editors), Western Ontario Series in Philosophy of Science, vol. 75, Springer, 2011, pp. 135-152. · Zbl 1259.03075
[63] Jech, T., On Gödel’s second incompleteness theorem. Proceedings of the American Mathematical Society, vol. 121 (1994), no. 1, pp. 311-313. · Zbl 0797.03059
[64] Jeřábek, E., Recursive functions and existentially closed structures. Journal of Mathematical Logic, vol. 20 No. 01, 2050002 (2020). · Zbl 1484.03126
[65] Jones, J. P. and Shepherdson, J. C., Variants of Robinson’s essentially undecidable theory. R. Archive for Mathematical Logic, vol. 23 (1983), pp. 65-77.
[66] Kanamori, A. and Mcaloon, K., On Gödel’s incompleteness and finite combinatorics. Annals of Pure Applied Logic, vol. 33 (1987), no. 1, pp. 23-41. · Zbl 0627.03041
[67] Kaye, R. and Kotlarski, H., On models constructed by means of the arithmetized completeness theorem. Mathematical Logic Quarterly, vol. 46 (2000), no. 4, pp. 505-516. · Zbl 0963.03061
[68] Kikuchi, M., A note on Boolos’ proof of the incompleteness theorem. Mathematical Logic Quarterly, vol. 40 (1994), pp. 528-532. · Zbl 0805.03052
[69] Kikuchi, M., Kolmogorov complexity and the second incompleteness theorem. Archive for Mathematical Logic, vol. 36 (1997), no. 6, pp. 437-443. · Zbl 0883.03042
[70] Kikuchi, M. and Kurahashi, T., Three short stories around Gödel’s incompleteness theorems (in Japanese), Journal of the Japan Association for Philosophy of Science, vol. 38 (2011), no. 2, pp. 27-32.
[71] Kikuchi, M. and Kurahashi, T., Generalizations of Gödel’s incompleteness theorems for \({\varSigma}_n\) -definable theories of arithmetic. The Review of Symbolic Logic, vol. 10 (2017), no. 4, pp. 603-616. · Zbl 1426.03038
[72] Kikuchi, M. and Kurahashi, T., Universal Rosser predicates. The Journal of Symbolic Logic, vol. 82 (2017), no. 1, pp. 292-302. · Zbl 1419.03034
[73] Kikuchi, M., Kurahashi, T., and Sakai, H., On proofs of the incompleteness theorems based on Berry’s paradox by Vopěnka, Chaitin, and Boolos. Mathematical Logic Quarterly, vol. 58 (2012), no. 4-5, pp. 307-316. · Zbl 1257.03088
[74] Kikuchi, M. and Tanaka, K., On formalization of model-theoretic proofs of Gödel’s theorems. Notre Dame Journal of Formal Logic, vol. 35 (1994), no. 3, pp. 403-412. · Zbl 0822.03032
[75] Kirby, L., Flipping properties in arithmetic. The Journal of Symbolic Logic, vol. 47 (1982), no. 2, pp. 416-422. · Zbl 0488.03031
[76] Kleene, S. C., A symmetric form of Godel’s theorem. Indagationes Mathematicae, vol. 12 (1950), pp. 244-246. · Zbl 0038.03101
[77] Kotlarski, H., On the incompleteness theorems. The Journal of Symbolic Logic, vol. 59 (1994), no. 4, pp. 1414-1419. · Zbl 0816.03025
[78] Kotlarski, H., Other proofs of old results. Mathematical Logic Quarterly, vol. 44 (1998), pp. 474-480. · Zbl 0924.03109
[79] Kotlarski, H., The incompleteness theorems after 70 years. Annals of Pure and Applied Logic, vol. 126 (2004), no. 1-3, pp. 125-138. · Zbl 1053.03033
[80] Kreisel, G., Note on arithmetic models for consistent formulae of the predicate calculus. Fundamenta Mathematicae, vol. 37 (1950), pp. 265-285. · Zbl 0040.00302
[81] Kreisel, G., On weak completeness of intuitionistic predicate logic. The Journal of Symbolic Logic, vol. 27 (1962), pp. 139-158. · Zbl 0117.01005
[82] Kreisel, G., A survey of proof theory. The Journal of Symbolic Logic, vol. 33 (1968), pp. 321-388. · Zbl 0177.01002
[83] Kritchman, S. and Raz, R., The surprise examination paradox and the second incompleteness theorem. Notices of the American Mathematical Society, vol. 57 (2010), no. 11, pp. 1454-1458. · Zbl 1261.03159
[84] Leach-Krouse, G., Yablifying the Rosser sentence. Journal of Philosophical Logic, vol. 43 (2014), pp. 827-834. · Zbl 1302.03073
[85] Kurahashi, T., Rosser-type undecidable sentences based on Yablo’s paradox. Journal of Philosophical Logic, vol. 43 (2014), pp. 999-1017. · Zbl 1339.03055
[86] Kurahashi, T., Arithmetical completeness theorem for modal logic. \( \boldsymbol{K} \). Studia Logica, vol. 106 (2018), no. 2, pp. 219-235. · Zbl 1437.03090
[87] Kurahashi, T., Arithmetical soundness and completeness for \(\ {\varSigma}_2\) numerations. Studia Logica, vol. 106 (2018), no. 6, pp. 1181-1196. · Zbl 1437.03167
[88] Kurahashi, T., A note on derivability conditions. The Journal of Symbolic Logic, 2020, to appear, doi:10.1017/jsl.2020.33. · Zbl 1473.03037
[89] Kurahashi, T., Rosser provability and the second incompleteness theorem. Symposium on Advances in Mathematical Logic 2018 Proceedings, to appear.
[90] Li, M. and Vitányi, P. M. B., Kolmogorov complexity and its applications, Handbook of Theoretical Computer Science (Van Leeuwen, J., editor), Elsevier, Amsterdam, 1990, pp. 187-254. · Zbl 0900.68264
[91] Lindström, P., Aspects of Incompleteness, Lecture Notes in Logic, vol. 10, Cambridge University Press, Cambridge, 2017. · Zbl 0882.03054
[92] Löb, M. H., Solution of a problem of Leon Henkin. The Journal of Symbolic Logic, vol. 20 (1955), no. 2, pp. 115-118. · Zbl 0067.00202
[93] Mills, G., A tree analysis of unprovable combinatorial statements. Model Theory of Algebra and Arithmetic, Lecture Notes in Mathematics, vol. 834, Springer, Berlin, 1980, pp. 248-311. · Zbl 0472.05019
[94] Montagna, F., On the formulas of Peano arithmetic which are provably closed under modus ponens. Bollettino dell’Unione Matematica Italiana, vol. 16 (1979), no. B5, pp. 196-211. · Zbl 0405.03030
[95] Mostowski, A., A generalization of the incompleteness theorem. Fundamenta Mathematicae, vol. 49 (1961), pp. 205-232. · Zbl 0099.00604
[96] Mostowski, A., Thirty years of foundational studies: Lectures on the development of mathematical logic and the study of the foundations of mathematics in 1930-1964. Acta Philosophica Fennica, vol. 17 (1965), pp. 1-180. · Zbl 0146.24504
[97] Murawski, R., Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Gödel’s Theorems, Synthese Library, vol. 286, Springer, Amsterdam, 2013. · Zbl 0934.03001
[98] Nelson, E., Predicative Arithmetic, Mathematical Notes, Princeton University Press, Princeton, NJ, 2014.
[99] Niebergall, K. G., Natural representations and extensions of Gödel’s second theorem, Logic Colloquium 01 (Baaz, M., Friedman, S. D., and Krajĺček, J., editors), Lecture Notes in Logic, vol. 20, The Association for Symbolic Logic, 2005, pp. 350-368. · Zbl 1081.03058
[100] Odifreddi, P., Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Elsevier, Amsterdam, 1992. · Zbl 0744.03044
[101] Pacholski, L. and Wierzejewski, J., Model Theory of Algebra and Arithmetic, Lecture Notes in Mathematics, vol. 834, Springer, Berlin, 1980. · Zbl 0436.00008
[102] Pakhomov, F., A weak set theory that proves its own consistency, preprint, 2019, arXiv:1907.00877v2.
[103] Paris, J. and Harrington, L., A mathematical incompleteness in Peano arithmetic. Handbook of Mathematical Logic (Barwise, J., editor), Studies in Logic and Foundations of Mathematics, vol. 90, Elsevier, Amsterdam, 1982, pp. 1133-1142. · Zbl 0528.03001
[104] Paris, J. and Kirby, L., Accessible independence results for Peano arithmetic. The Bulletin of the London Mathematical Society, vol. 14 (1982), no. 4, pp. 285-293. · Zbl 0501.03017
[105] Pour-El, M. B. and Kripke, S., Deduction-preserving “recursive isomorphisms” between theories. Fundamenta Mathematicae, vol. 61 (1967), pp. 141-163. · Zbl 0174.02003
[106] Priest, G., Yablo’s paradox. Analysis, vol. 57 (1997), no. 4, pp. 236-242. · Zbl 0943.03588
[107] Pudlák, P., Another combinatorial principle independent of Peano’s axioms, unpublished manuscript, 1979.
[108] Pudlák, P., Cuts, consistency statements and interpretations. The Journal of Symbolic Logic, vol. 50 (1985), pp. 423-441. · Zbl 0569.03024
[109] Pudlák, P., Incompleteness in the finite domain. The Bulletin of Symbolic Logic, vol. 23 (2017), no. 4, pp. 405-441. · Zbl 1423.03245
[110] Robinson, A., On languages which are based on non-standard arithmetic. Nagoya Mathematical Journal, vol. 22 (1963), pp. 83-117. · Zbl 0166.26101
[111] Rosser, J. B., Extensions of some theorems of Gödel and Church. The Journal of Symbolic Logic, vol. 1 (1936), no. 3, pp. 87-91. · JFM 62.1058.03
[112] Russell, B., Mathematical logic as based on the theory of types. American Journal of Mathematics, vol. 30 (1908), pp. 222-262. · JFM 39.0085.03
[113] Salehi, S. and Seraji, P., Gödel-Rosser’s incompleteness theorem, generalized and optimized for definable theories. Journal of Logic and Computation, vol. 27 (2017), no. 5, pp. 1391-1397. · Zbl 1444.03166
[114] Salehi, S. and Seraji, P., On constructivity and the Rosser property: A closer look at some Gödelean proofs. Annals of Pure and Applied Logic, vol. 169 (2018), pp. 971-980. · Zbl 1434.03135
[115] Simpson, S. G., Harvey Friedman&s Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, Elsevier, Amsterdam, 1985. · Zbl 0588.03001
[116] Simpson, S. G. (ed.), Logic and Combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, RI, 1987.
[117] Simpson, S. G., Subsystems of Second-Order Arithmetic, Perspectives in Logic, vol. 1, Cambridge University Press, Cambridge, 2009. · Zbl 1181.03001
[118] Smith, P., An Introduction to Gödel’s Theorems, Cambridge University Press, Cambridge, 2013. · Zbl 1270.03002
[119] Smoryński, C., The incompleteness theorems, Handbook of Mathematical Logic (Barwise, J., editor), Elsevier, Amsterdam, 1982, pp. 821-865.
[120] Smullyan, R. M., Gödel’s Incompleteness Theorems, Oxford Logic Guides, vol. 19, Oxford University Press, Oxford, 1992. · Zbl 0787.03003
[121] Smullyan, R. M., Diagnolisation and Self-Reference, Oxford Logic Guides, vol. 27, Clarendon Press, Oxford, 1994. · Zbl 0810.03001
[122] Solovay, R. M., Provability interpretations of modal logic. Israel Journal of Mathematics, vol. 25 (1976), pp. 287-304. · Zbl 0352.02019
[123] Švejdar, V., An interpretation of Robinson arithmetic in its Grzegorczyk’s weaker variant. Fundamenta Informaticae, vol. 81 (2007), no. 1-3, pp. 347-354. · Zbl 1135.03023
[124] Tarski, A. and Givant, S., Tarski’s system of geometry. The Bulletin of Symbolic Logic, vol. 5 (1999), no. 2, pp. 175-214. · Zbl 0932.01031
[125] Tarski, A., Mostowski, A., and Robinson, R. M., Undecidabe Theories, Studies in Logic and the Foundations of Mathematics, vol. 13, Elsevier, Amsterdam, 1953. · Zbl 0053.00401
[126] Turing, A., Systems of logic based on ordinals. Proceedings of the London Mathematical Society, vol. 45 (1939), pp. 161-228. · Zbl 0021.09704
[127] Vaught, R. L., On a theorem of Cobham concerning undecidable theories, Proceedings of the 1960 International Congress on Logic, Methodology and Philosophy of Science (Nagel, E.Suppes, P., and Tarski, P., editors), Stanford University Press, Stanford, 1962, pp. 14-25. · Zbl 0178.32303
[128] Visser, A., The provability logics of recursively enumerable theories extending Peano arithmetic at arbitrary theories extending Peano arithmetic. Journal of Philosophical Logic, vol. 13 (1984), no. 2, pp. 181-212. · Zbl 0581.03009
[129] Visser, A., Growing commas: A study of sequentiality and concatenation. Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 1, pp. 61-85. · Zbl 1190.03052
[130] Visser, A., Can we make the second incompleteness theorem coordinate free?Journal of Logic and Computation, vol. 21 (2011), no. 4, pp. 543-560. · Zbl 1262.03123
[131] Visser, A., Why the theory R is special. Foundational Adventures: Essay in Honour of Harvey Friedman, College Publications, 2014, pp. 7-23. · Zbl 1358.03091
[132] Visser, A., On Q. Soft Computing, vol. 21 (2016), pp. 39-56. · Zbl 1420.03143
[133] Visser, A., The second incompleteness theorem: Reflections and ruminations, Gödel’s Disjunction: The Scope and Limits of Mathematical Knowledge (Horsten, L. and Welch, P., editors), Oxford University Press, Oxford, 2016, pp. 67-91. · Zbl 1433.03141
[134] Visser, A., The interpretation existence lemma. Feferman on Foundations: Logic, Mathematics, Philosophy, Outstanding Contributions to Logic, vol. 13, Springer, Cham, Switzerland, 2018, pp. 101-144. · Zbl 1429.03212
[135] Visser, A., From Tarski to Gödel: Or, how to derive the second incompleteness theorem from the undefinability of truth without self-reference. Journal of Logic and Computation, vol. 29 (2019), no. 5, pp. 595-604. · Zbl 1444.03167
[136] Visser, A., Another look at the second incompleteness theorem. Review of Symbolic Logic, vol. 13 (2020), no. 2, pp. 269-295. · Zbl 1444.03168
[137] Vopěnka, P., A new proof of Gödel’s result on non-provability of consistency. Bulletin del’Académie Polonaise des Sciences. Série des Sciences Mathématiques. Astronomiques et Physiques, vol. 14 (1966), pp. 111-116. · Zbl 0156.25003
[138] Wang, H., Undecidable sentences generated by semantic paradoxes. Journal of Symbolic Logic, vol. 20 (1955), no. 1, pp. 31-43. · Zbl 0064.24501
[139] Weiermann, A., An application of graphical enumeration to PA. Journal of Symbolic Logic, vol. 68 (2003), no. 1, pp. 5-16. · Zbl 1041.03045
[140] Weiermann, A., A classification of rapidly growing Ramsey functions. Proceedings of the American Mathematical Society, vol. 132 (2004), pp. 553-561. · Zbl 1041.03044
[141] Weiermann, A., Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results. Annals of Pure and Applied Logic, vol. 136 (2005), pp. 189-218. · Zbl 1090.03028
[142] Weiermann, A., Classifying the provably total functions of PA, this Journal, vol. 12 (2006), no. 2, pp. 177-190. · Zbl 1118.03053
[143] Weiermann, A., Phase transition thresholds for some Friedman-style independence results. Mathematical Logic Quarterly, vol. 53 (2007), no. 1, pp. 4-18. · Zbl 1110.03051
[144] Willard, D. E., Self-verifying axiom systems, the incompleteness theorem and related reflection principles. Journal of Symbolic Logic, vol. 66 (2001), no. 2, pp. 536-596. · Zbl 0991.03053
[145] Willard, D. E., A generalization of the second incompleteness theorem and some exceptions to it. Annals of Pure and Applied Logic, vol. 141 (2006), no. 3, pp. 472-496. · Zbl 1103.03059
[146] Yablo, S., Paradox without self-reference. Analysis, vol. 53 (1993), no. 4, pp. 251-252. · Zbl 0943.03565
[147] Zach, R., Hilbert’s program then and now. Philosophy of Logic, Handbook of the Philosophy of Science, Elsevier, Amsterdam, 2006, pp. 411-447.
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.