Hostname: page-component-8448b6f56d-jr42d Total loading time: 0 Render date: 2024-04-24T03:49:49.343Z Has data issue: false hasContentIssue false
  • English
  • Français

Σ2 Induction and infinite injury priority argument, Part I: Maximal sets and the jump operator

Published online by Cambridge University Press:  12 March 2014

C. T. Chong  and
Yue Yang
C. T. Chong
Affiliation:
Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, Singapore 119260, E-mail: chongct@math.nus.edu.sg
Yue Yang
Affiliation:
Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, Singapore 119260, E-mail: matyangy@nus.edu.sg
Get access Rights & Permissions [Opens in a new window]

Extract

The study of recursion theory on models of fragments of Peano arithmetic has hitherto been concentrated on recursively enumerable (r.e.) sets and their degrees (with a few exceptions, such as that in [2] on minimal degrees). The reason for such a concerted effort is clear: priority arguments have occupied a central position in post Friedberg-Muchnik recursion theory, and after almost forty years of intensive development in the subject, they are still the essential tools on which investigations of r.e. sets and their degrees depend. There are two possible approaches to the study within fragments of arithmetic: To give a general analysis of strategies, and identify their proof-theoretic strengths (for example in [6] on infinite injury priority methods), or to consider specific theorems in recursion theory, and, if possible, pinpoint the exact levels of induction provably equivalent to the theorems. The work reported in this paper belongs to the second approach. More precisely, we single out two infinitary injury type constructions of r.e. sets—one concerning maximal sets and the other based on the notion of the jump operator—to be the topics of study.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 3 , September 1998 , pp. 797 - 814
Copyright
Copyright © Association for Symbolic Logic 1998

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., Maximal sets and fragments of Peano arithmetic, Nagoya Journal of Mathematics, vol. 115 (1989), pp. 165–183.CrossRefGoogle Scholar
[2]Chong, C. T. and Mourad, K. J., The degree of a Σn cut, Annals of Pure and Applied Logic, vol. 48 (1990), pp. 227–235.CrossRefGoogle Scholar
[3]Chong, C. T. and Mourad, K. J.definable sets without Σn induction, Transactions of the American Mathematical Society, vol. 334 (1992), pp. 349–363.Google Scholar
[4]Groszek, M. J. and Mytilinaios, M. E.,Σ2-induction and the construction of a high degree, Recursion theory week, Proc. Oberwolfach 1989 (Ambos-Spies, K.et al., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, Berlin, 1990, pp. 205–223.Google Scholar
[5]Groszek, M. J., Mytilinaios, M. E., and Slaman, T. A., The Sacks density theorem and Σ2-bounding, this Journal, to appear.Google Scholar
[6]Groszek, M. J. and Slaman, T. A., Foundations of the priority method I—finite and infinite injury, preprint.Google Scholar
[7]Groszek, M. J. and Slaman, T. A., On Turing reducibility, preprint.Google Scholar
[8]Kaye, R., Models of Peano arithmetic, Oxford Logic Guides, vol. 15, Clarendon Press, Oxford, 1991.CrossRefGoogle Scholar
[9]Mourad, J., Ph.D. thesis, University of Chicago, 1988.Google Scholar
[10]Mytilinaios, M. E., Finite injury and Σ1-induction, this Journal, vol. 54 (1989), pp. 38–49.Google Scholar
[11]Mytilinaios, M. E. and Slaman, T. A., Σ2-collection and the infinite injury priority method, this Journal, vol. 54 (1989), pp. 38–49.Google Scholar
[12]Paris, J. B. and Kirby, L. A. S., Σn-cottection schemas in arithmetic, Logic colloquium 77, North-Holland, Amsterdam, 1978, pp. 199–209.CrossRefGoogle Scholar
[13]Shore, R. A., Splitting an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 204, pp. 65–78.Google Scholar
[14]Slaman, T. A. and Woodin, W. H., Σ1-collection and the finite injury priority method, Mathematical logic and its applications, Lecture Notes in Mathematics, vol. 1388, Springer-Verlag, Berlin, 1989.Google Scholar
[15]Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[16]Yang, Y., The thickness lemma from P- +IΣ1 + ┐BΣ2, this Journal, vol. 60 (1995), pp. 505–511.Google Scholar