Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-26T03:20:30.665Z Has data issue: false hasContentIssue false
  • English
  • Français

The Sacks density theorem and Σ2-bounding

Published online by Cambridge University Press:  12 March 2014

Marcia J. Groszek ,
Michael E. Mytilinaios  and
Theodore A. Slaman
Marcia J. Groszek
Affiliation:
Department of Mathematics, Dartmouth College, Hanover New Hampshire 03755, USA, E-mail: [email protected]
Michael E. Mytilinaios
Affiliation:
Department of Informatics, Athens University of Economics, Patission 76, Athens 104 34, Greece, E-mail: [email protected]
Theodore A. Slaman
Affiliation:
Department of Mathematics, The University of Chicago, Chicago, Illinois 60637, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P− + BΣ2. The proof has two components: a lemma that in any model of P− + BΣ2, if B is recursively enumerable and incomplete then IΣ1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 2 , June 1996 , pp. 450 - 467
Copyright
Copyright © Association for Symbolic Logic 1996

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. and Mourad, K. J., Σn definability without Σn induction, Transactions of the American Mathematical Society, vol. 334 (1992), pp. 349–363.Google Scholar
[2]Groszek, M. J. and Mytilinaios, M. E., Σ2-induction and the construction of a high degree, Recursion theory week, Oberwolfach 1989 (Ambos-Spies, K., Muller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, New York, 1990, pp. 205–223.Google Scholar
[3]Groszek, M. J. and Slaman, T. A., On Turing reducibility, preprint, 1994.Google Scholar
[4]Mytilinaios, M. E., Finite injury and Σ2-induction, this Journal, vol. 54 (1989), pp. 38–49.Google Scholar
[5]Mytilinaios, M. E. and Slaman, T. A., Σ2-collection and the infinite injury priority method, this Journal, vol. 53 (1988), pp. 212–221.Google Scholar
[6]Sacks, G. E., On the degrees less than 0′, Annals of Mathematics, vol. 77 (1963), pp. 211–231.CrossRefGoogle Scholar
[7]Sacks, G. E., The recursively enumerable degrees are dense, Annals of Mathematics, vol. 80 (1964), pp. 300–312.Google Scholar
[8]Sacks, G. E. and Simpson, S. G., The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343–367.CrossRefGoogle Scholar
[9]Shore, R. A., The recursively enumerable α-degrees are dense, Annals of Mathematical Logic, vol. 9 (1976), pp. 123–155.Google Scholar
[10]Slaman, T. A. and Woodin, W. H., Σ-collection and the finite injury method, Mathematical logic and applications (Shinoda, J., Slaman, T. A., and Tugué, T., editors), Springer-Verlag, Heidelberg, 1989, pp. 178–188.Google Scholar
[11]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Heidelberg, 1987.Google Scholar