Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-28T01:03:49.793Z Has data issue: false hasContentIssue false
  • English
  • Français

Relative enumerability in the difference hierarchy

Published online by Cambridge University Press:  12 March 2014

Marat M. Arslanov ,
Geoffrey L. Laforte  and
Theodore A. Slaman
Marat M. Arslanov
Affiliation:
13 Karbishev St. No. 109, Kazan 420087, Russia, E-mail: [email protected]
Geoffrey L. Laforte
Affiliation:
Institute for Human and Machine Cognition, University of West Florida, 11000 University Parkway, Pensacola, FL 32514, USA, E-mail: [email protected]
Theodore A. Slaman
Affiliation:
Department of Mathematics, The University of California, Berkeley, CA 94720-3840, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 2 , June 1998 , pp. 411 - 420
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] Arslanov, M. M., On the upper semilattice of Turing degrees below 0′, Soviet Mathematics, vol. 7 (1986), pp. 27–33.Google Scholar
[2] Arslanov, M. M., Lempp, S., and Shore, R. A., Interpolating d.r.e. and RE A degrees between r.e. degrees, to appear in Annals of Pure and Applied Logic.Google Scholar
[3] Arslanov, M. M., On isolating r.e. and isolated d.r.e. degrees, Computability, enumerability, unsolvability (Cooper, S. B. et al., editors), London Mathematical Society Lecture Notes, no. 224, Cambridge University Press, 1996, pp. 61–80.Google Scholar
[4] Cholak, P. and Hinman, P., Iterated relative recursive enumerability, Archive for Mathematical Logic, vol. 33 (1994), pp. 321–346.Google Scholar
[5] Cooper, S. B., Lempp, S., and Watson, P., Weak density and cupping in the d.r.e. degrees, Israel Journal of Mathematics, vol. 67 (1989), pp. 137–152.Google Scholar
[6] Cooper, S. B. and Yi, X., Isolated d.r.e. degrees, to appear, 1996.Google Scholar
[7] Ershov, Y. L., A hierarchy of sets, part I, Algebra and Logic, vol. 7 (1968), pp. 24–43.Google Scholar
[8] Jockusch, C. and Shore, R., Pseudojump operators II: Transfinite iterations, hierarchies, and minimal covers, this Journal, vol. 49 (1984), pp. 1205–1236.Google Scholar
[9] Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 16 (1966), pp. 537–569.Google Scholar
[10] LaForte, G., Phenomena in the n-r.e. and n-REA degrees, Ph.D. thesis , University of Michigan, Ann Arbor, 1995.Google Scholar
[11] LaForte, G., The isolated d.r.e. degrees are dense in the r.e. degrees, Mathematical Logic Quarterly, vol. 42 (1996), no. 2.Google Scholar
[12] Putnam, H., Trial and error predicates and the solution to a problem of Mostowski, this Journal, vol. 30 (1965), pp. 49–57.Google Scholar
[13] Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.Google Scholar
[14] Soare, R. I. and Stob, M., Relative recursive enumerability, Proceedings of the Herbrand symposium logic colloquium '81 (Stern, J., editor), North-Holland, Amsterdam, 1982, pp. 299–324.Google Scholar