Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T14:54:09.407Z Has data issue: false hasContentIssue false
  • English
  • Français

Friedberg Numbering in Fragments of Peano Arithmetic and α-Recursion Theory

Published online by Cambridge University Press:  12 March 2014

Wei Li
Wei Li*
Affiliation:
Department of Mathematics, National University of Singapore, 119076, Singapore, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we investigate the existence of a Friedberg numbering in fragments of Peano Arithmetic and initial segments of Gödel's constructible hierarchy Lα, where α is Σ1 admissible. We prove that

(1) Over P− + BΣ2, the existence of a Friedberg numbering is equivalent to IΣ2, and

(2) For Lα, there is a Friedberg numbering if and only if the tame Σ2 projectum of α equals the Σ2 cofinality of α.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 4 , December 2013 , pp. 1135 - 1163
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Chong, C. T., Techniques of admissible recursion theory, Lecture Notes in Mathematics, vol. 1106, Springer-Verlag, 1984.CrossRefGoogle Scholar
[2] Chong, C. T., Maximal sets and fragments of Peano arithmetic, Nagoya Mathematical Journal, vol. 115 (1989), pp. 165–183.CrossRefGoogle Scholar
[3] Chong, C. T., Recursively enumerable sets in models of Σ2 collection, Mathematical logic andapplications, Lecture Notes in Mathematics, vol. 1388, 1989, pp. 1–15.CrossRefGoogle Scholar
[4] Chong, C. T. and Mourad, K. J., The degree of a Σn cut, Annals of Pure and Applied Logic, vol. 48 (1990), no. 3, pp. 227–235.Google Scholar
[5] Chong, C. T., Qian, Lei, Slaman, T., and Yang, Yue, Σ2 induction and infinite injury priority arguments, part III: prompt sets, minimal pairs and Shoenfield's conjecture, Israel Journal of Mathematics, vol. 121 (2001), pp. 1–28.Google Scholar
[6] Chong, C. T. and Yang, Yue, Recursion theory on weak fragments of Peano arithmetic: a study of definable cuts, Proceedings of the sixth Asian Logic Conference, 1996, pp. 47–65.Google Scholar
[7] Chong, C. T. and Yang, Yue, Σ2 induction and infinite injury priority argument, Part I: maximal sets and the jump operator, this Journal, vol. 63 (1998), pp. 797–814.Google Scholar
[8] Friedberg, R. M., Three theorems on recursive enuemration I. Decomposition. II. Maximal set. III. Enumeration without duplication, this Journal, vol. 23 (1958), pp. 309–316.Google Scholar
[9] Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.CrossRefGoogle Scholar
[10] Groszek, M. and Slaman, T., On Turing reducibility.Google Scholar
[11] Jain, Sanjay and Stephan, Frank, Numberings optimal for learning, Journal of Computer and System Sciences, vol. 76 (2010), pp. 233–250.CrossRefGoogle Scholar
[12] Jensen, R., The fine structure of the constructive hierarchy, Annals of Mathematical Logic, vol. 4 (1972), pp. 229–308.CrossRefGoogle Scholar
[13] Kaye, Richard, Model-theoretic properties characterizing Peano arithmetic, this Journal, vol. 56 (1991), no. 3, pp. 949–963.Google Scholar
[14] Kaye, Richard, Models of Peano Arithmetic, Oxford University Press, 1991.CrossRefGoogle Scholar
[15] Kummer, Martin, An easy priority-free proof of a theorem of Friedberg, Theoretical Computer Science, vol. 74 (1990), pp. 249–251.Google Scholar
[16] Lerman, Manuel, On suborderings of the α-recursively enuemrable α-degrees, Annals of Mathematical Logic, vol. 4 (1972), pp. 396–392.Google Scholar
[17] Lerman, Manuel, Maximal α-r.e. sets, Transactions of the American Mathematical Society, vol. 188 (1974), no. 2, pp. 341–386.Google Scholar
[18] Lerman, Manuel and Sacks, Gerald E., Some minimal pairs of α-recursively enumerable degrees, Annals of Mathematical Logic, vol. 4 (1972), pp. 415–442.Google Scholar
[19] Mytilinaios, M. and Slaman, T., Σ2-collection and the infinite injury priority method, this Journal, vol. 53 (1988), pp. 212–221.Google Scholar
[20] Paris, J. B. and Kirby, L. A. S., Σn-collection schemas in arithmetic, Logic colloquium '77, North Holland, Amsterdam, 1978, pp. 199–209.Google Scholar
[21] Sacks, Gerald E., Higher recursion theory, Springer, 2010.Google Scholar
[22] Sacks, Gerald E. and Simpson, S. G., The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343–367.Google Scholar
[23] Slaman, Theodore A. and Woodin, W. Hugh, Σ1 collection and the finite injury priority method, Mathematical logic and its applications (Shinoda, J., Slaman, T. A., and Tugue, T., editors), Lecture Notes in Mathematics, vol. 1388, Springer, 1989, pp. 178–188.Google Scholar
[24] Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Heidelberg, 1987.CrossRefGoogle Scholar