×

zbMATH — the first resource for mathematics

Incompleteness and jump hierarchies. (English) Zbl 07243364
Summary: This paper is an investigation of the relationship between Gödel’s second incompleteness theorem and the well-foundedness of jump hierarchies. It follows from a classic theorem of Spector that the relation \(\{(A,B)\in\mathbb{R}^2:\mathcal{O}^A\leq_HB\}\) is well-founded. We provide an alternative proof of this fact that uses Gödel’s second incompleteness theorem instead of the theory of admissible ordinals. We then derive a semantic version of the second incompleteness theorem, originally due to Mummert and Simpson, from this result. Finally, we turn to the calculation of the ranks of reals in this well-founded relation. We prove that, for any \(A\in\mathbb{R}\), if the rank of \(A\) is \(\alpha\), then \(\omega_1^A\) is the \((1+\alpha)\) th admissible ordinal. It follows, assuming suitable large cardinal hypotheses, that, on a cone, the rank of \(X\) is \(\omega_1^X\).
MSC:
03F35 Second- and higher-order arithmetic and fragments
03D55 Hierarchies of computability and definability
03F40 Gödel numberings and issues of incompleteness
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beklemishev, Lev D., Provability algebras and proof-theoretic ordinals. I, Ann. Pure Appl. Logic, 128, 1-3, 103-123 (2004) · Zbl 1048.03045
[2] Enderton, H. B.; Putnam, Hilary, A note on the hyperarithmetical hierarchy, J. Symbolic Logic, 35, 429-430 (1970) · Zbl 0205.30803
[3] Friedman, Harvey, Uniformly defined descending sequences of degrees, J. Symbolic Logic, 41, 2, 363-367 (1976) · Zbl 0366.02030
[4] Harrison, Joseph, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc., 131, 526-543 (1968) · Zbl 0186.01101
[5] kennedy2015incompleteness Juliette Kennedy, \newblock Did the Incompleteness Theorems Refute Hilbert’s Program?, \newblock Stanford Encyclopedia of Philosophy, 2015.
[6] kripke2009collapse S. Kripke, \newblock The Collapse of the Hilbert Program: Why a System Cannot Prove its Own 1-consistency, \newblock Bull. Symbolic Logic <span class=”textbf”>1</span>5 (2009), no. 2, 229-230.
[7] Mummert, Carl; Simpson, Stephen G., An incompleteness theorem for \(\beta_n\)-models, J. Symbolic Logic, 69, 2, 612-616 (2004) · Zbl 1075.03031
[8] pakhomov2018reflection Fedor Pakhomov and James Walsh, \newblock Reflection ranks and ordinal analysis, \newblock arXiv preprint \arXiv 1805.02095 (2018).
[9] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Logic, xvi+444 pp. (2009), Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY · Zbl 1181.03001
[10] Steel, John, Descending sequences of degrees, J. Symbolic Logic, 40, 1, 59-61 (1975) · Zbl 0349.02036
[11] Steel, John R., Forcing with tagged trees, Ann. Math. Logic, 15, 1, 55-74 (1978) · Zbl 0404.03020
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.