Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-28T03:43:57.306Z Has data issue: false hasContentIssue false
  • English
  • Français

A hierarchy for the plus cupping Turing degrees

Published online by Cambridge University Press:  12 March 2014

Yong Wang  and
Angsheng Li
Yong Wang
Affiliation:
Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing 100080, P. R. China, E-mail: [email protected]
Angsheng Li
Affiliation:
Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing 100080, P. R. China School of Information Science, Beijing Normal University, Beijing, P. R. China, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We say that a computably enumerable (c. e.) degree a is plus-cupping, if for every c.e. degree x with 0 < x ≤ a, there is a c. e. degree y ≠ 0′ such that x ∨ y = 0′. We say that a is n-plus-cupping, if for every c. e. degree x, if 0 < x ≤ a, then there is a lown c. e. degree I such that x ∨ I = 0′. Let PC and PCn be the set of all plus-cupping, and n-plus-cupping c. e. degrees respectively. Then PC1 ⊆ PC2 ⊆ PC3 = PC. In this paper we show that PC1 ⊂ PC2, so giving a nontrivial hierarchy for the plus cupping degrees. The theorem also extends the result of Li, Wu and Zhang [14] showing that LC1 ⊂ LC2, as well as extending the Harrington plus-cupping theorem [8].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 68 , Issue 3 , September 2003 , pp. 972 - 988
Copyright
Copyright © Association for Symbolic Logic 2003

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] Ambos-Spies, K., Jockusch, C. G. Jr., Shore, R. A., and Soare, R. I., An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Transactions of the American Mathematical Society, vol. 281 (1984), pp. 109–128.CrossRefGoogle Scholar
[2] Cholak, P., Groszek, M., and Slaman, T. A., An almost deep degree, this Journal, vol. 66 (2001), no. 2, pp. 881–901.Google Scholar
[3] Cooper, S. B., Distinguishing the arithmetical hierarchy, preprint, Berkeley, 10 1972.Google Scholar
[4] Cooper, S. B., On a theorem of C. E. M. Yates, handwritten notes, 1974.Google Scholar
[5] Cooper, S. B. and Li, A., Splitting and nonsplitting, II: A Low2 computably enumerable degree above which 0′ is not splittable, this Journal, vol. 67 (2002), no. 4, pp. 1391–1430.Google Scholar
[6] Fejer, P. A. and Soare, R. I., The plus cupping theorem for the recursively enumerable degrees. Logic year 1979–80: University of Connecticut (Lerman, M., Schmerl, J. H., and Soare, R. I., editors), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, Heidelberg, Tokyo, New York, 1981.Google Scholar
[7] Harrington, L., On Cooper's proof of a theorem of Yates, handwritten notes, 1976.Google Scholar
[8] Harrington, L., Plus cupping in the recursively enumerable degrees, handwritten notes, 1978.Google Scholar
[9] Jockusch, C. G., Li, A., and Yang, Y., A join theorem for the computably enumerable degrees, to appear.Google Scholar
[10] 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
[11] Lachlan, A. H., Bounding minimal pairs, this Journal, vol. 44 (1979), pp. 626–642.Google Scholar
[12] Li, A., Elementary differences among jump hierarchies, to appear.Google Scholar
[13] Li, A., A hierarchy characterisation of the cuppable degrees, to appear.Google Scholar
[14] Li, A., Wu, G., and Zhang, Z., A hierarchy for the cuppable degrees, Illinois Journal of Mathematics, vol. 44 (Fall 2000), no. 3, pp. 619–632.CrossRefGoogle Scholar
[15] Robinson, R. W., Jump restricted interpolation in the recursively enumerable degrees, Annals of Mathematics, vol. 93 (1971), no. 2, pp. 586–596.Google Scholar
[16] Sacks, G. E., On the degrees less than 0′, Annals of Mathematics, vol. 77 (1963), no. 2, pp. 211–231.CrossRefGoogle Scholar
[17] Sacks, G. E., The recursively enumerable degrees are dense, Annals of Mathematics, vol. 80 (1964), no. 2, pp. 300–312.CrossRefGoogle Scholar
[18] Soare, R. I., Automorphisms of the lattice of recursively enumerable sets, Bulletin of the American Mathematical Society, vol. 80 (1974), pp. 53–58.CrossRefGoogle Scholar
[19] Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, 1987.Google Scholar
[20] Yates, C. E. M., A minimal pair of recursively enumerable degrees, this Journal, vol. 31 (1966), pp. 159–168.Google Scholar