Abstract
The foundation scheme in set theory asserts that every nonempty class has an \(\in \)-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and \(\alpha \)-recursion theory. We take KP set theory without foundation (called KP\(^-\)) as the base theory. We show that KP\(^-\) + \(\Pi _1\)-Foundation + \(V=L\) is enough to carry out finite injury arguments in \(\alpha \)-recursion theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this theory. In addition, we compare the strengths of some fragments of KP.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ackermann, W.: Die widerspruchsfreiheit der allgemeinen mengenlehre. Math. Ann. 114(1), 305–315 (1937)
Barwise, J.: Admissible Sets and Structures. Springer, Berlin (1975)
Cantini, A.: Nonextensional theories of predicative classes over PA. Rend. Sem. Mat. Univ. Politec. Torino 40(3), 47–79 (1984)
Cantini, A.: A note on the theory of admissible sets with \(\in \)-induction restricted to formulas with one quantifier and related systems. Boll. Un. Mat. Ital. B 2(3), 721–737 (1983)
Chong, C.T., Mourad, K.J.: The degree of a \(\Sigma _n\) cut. Ann. Pure Appl. Log. 48, 227–235 (1990)
Friedman, H.: Countable models of set theories. In: Mathias, A.R.D., Rogers, H. (eds.) Cambridge Summer School in Mathematical Logic. Lecture Notes in Mathematics, vol. 337, pp. 539–573. Springer, Berlin, Heidelberg (1973)
Friedman, S.D.: \(\beta \)-recursion theory. Trans. Am. Math. Soc. 255, 173–200 (1979)
Groszek, M.J., Mytilinaios, M.E., Slaman, T.A.: The Sacks density theorem and \(\Sigma _2\)-bounding. J. Symb. Log. 61(2), 450–467 (1996)
Jech, T.: Set Theory: The Third Millennium Edition, Revised and Expanded. Springer Monographs in Mathematics, 3rd edn. Springer, Berlin (2003)
Kaye, R., Wong, T.L.: On interpretations of arithmetic and set theory. Notre Dame J. Form. Log. 48(4), 497–510 (2007)
Kleene, S.C.: On the form of predicates in the theory of constructive ordinals (second paper). Am. J. Math. 77, 405–428 (1955)
Lerman, M., Sacks, G.E.: Some minimal pairs of \(\alpha \)-recursively enumerable degrees. Ann. Math. Log. 4, 415–442 (1972)
Lubarsky, R.S.: An introduction to \(\gamma \)-recursion theory (or what to do in \({\rm KP}\,-\,\) foundation). J. Symb. Log. 55(1), 194–206 (1990)
Maass, W.: On minimal pairs and minimal degrees in higher recursion theory. Arch. Math. Log. Grundlag. 18(3–4), 169–186 (1976)
Mytilinaios, M.: Finite injury and \(\Sigma _1\)-induction. J. Symb. Log. 54(1), 38–49 (1989)
Mytilinaios, M.E., Slaman, T.A.: \(\Sigma _2\)-collection and the infinite injury priority method. J. Symb. Log. 53(1), 212–221 (1988)
Paris, J.B., Kirby, L.A.S.: \(\Sigma _{n}\)-collection schemas in arithmetic. In: Logic Colloquium ’77 (Proceedings of Conference on Wrocław 1977), vol. 96 of Studies in Logic and the Foundations of Mathematics, pp. 199–209. North-Holland (1978)
Rathjen, M.: Fragments of Kripke–Platek set theory with infinity. In: Aczel, P., Simmons, H., Wainer, S.S. (eds.) Proof Theory (Leeds, 1990), pp. 251–274. Cambridge University Press, Cambridge (1993)
Rathjen, M.: A proof-theoretic characterization of the primitive recursive set functions. J. Symbol. Log. 57(3), 954–969 (1992)
Rathjen, M.: The natural numbers in constructive set theory. MLQ Math. Log. Q. 54(1), 83–97 (2008)
Ressayre, J.P.: Modèles non standard et sous-systèmes remarquables de \(\rm {ZF}\). In: Modèles Non standard en Arithmétique et théorie des ensembles, vol. 22 of Publications Mathématiques de l’Université Paris VII, pp. 47–147. Université de Paris VII, U.E.R. de Mathématiques, Paris (1987)
Sacks, G.E., Simpson, S.G.: The \(\alpha \)-finite injury method. Ann. Math. Log. 4, 343–367 (1972)
Shore, R.A.: Splitting an \(\alpha \)-recursively enumerable set. Trans. Am. Math. Soc. 204, 65–77 (1975)
Shore, R.A.: The recursively enumerable \(\alpha \)-degrees are dense. Ann. Math. Log. 9(1–2), 123–155 (1976)
Shore, R.A.: Some more minimal pairs of \(\alpha \)-recursively enumerable degrees. Z. Math. Log. Grundlag. Math. 24(5), 409–418 (1978)
Slaman, T.A.P.: \(\Sigma _n\)-bounding and \(\Delta _n\)-induction. Proc. Am. Math. Soc. 132(8), 2449–2456 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Wei Li research was supported by FWF–RFBR Joint Project I1238, “Definability and Computability”. Tin Lok Wong was financially supported by FWF Project P 24654 N25, “The Infinity Project”. Sy-David Friedman was supported by both projects.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Friedman, SD., Li, W. & Wong, T.L. Fragments of Kripke–Platek set theory and the metamathematics of \(\alpha \)-recursion theory. Arch. Math. Logic 55, 899–924 (2016). https://doi.org/10.1007/s00153-016-0501-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-016-0501-z