Article contents
The distribution of properly Σ20 e-degrees
Published online by Cambridge University Press: 12 March 2014
Abstract
We show that for every enumeration degree a < 0′e there exists an e-degree c such that a ≤ c < 0′e, and all degrees b, with c ≤ b < 0′e, are properly Σ20.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2000
References
REFERENCES
[1]Calhoun, W. C. and Slaman, T. A., The Π21 e-degrees are not dense, this Journal, vol. 61 (1996), pp. 1364–1379.Google Scholar
[2]Cooper, S. B., Partial degrees and the density problem. Part 2: The enumeration degrees of the 2 sets are dense, this Journal, vol. 49 (1984), pp. 503–513.Google Scholar
[3]Cooper, S. B., Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion theory week, Oberwolfach 1989 (Ambos-Spies, K., MÜller, G., and Sacks, G. E., editors), Lecture Notes in Mathematics, no. 1432, Springer-Verlag, Heidelberg, 1990, pp. 57–110.Google Scholar
[4]Cooper, S. B. and Copestake, C. S., Properly 2 enumeration degrees, Zeitschrift fÜr Mathematische Logik und Grundlagen der Mathematik, vol. 34 (1988), pp. 491–522.CrossRefGoogle Scholar
[5]McEvoy, K., Jumps of quasi-minimal enumeration degrees, this Journal, vol. 50 (1985), pp. 839–848.Google Scholar
[6]McEvoy, K. and Cooper, S. B., On minimal pairs of enumeration degrees, this Journal, vol. 50 (1985), pp. 983–1001.Google Scholar
[7]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[8]Shoenfield, J. R., On degrees of unsolvability, Annals of Mathematics, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[9]Sorbi, A., The enumeration degrees of the 20 sets, Complexity, logic and recursion theory (Sorbi, A., editor), Marcel Dekker, New York, 1997, pp. 303–330.Google Scholar
- 1
- Cited by