Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A join theorem for the computably enumerable degrees

Authors: Carl G. Jockusch Jr., Angsheng Li and Yue Yang
Translated by:
Journal: Trans. Amer. Math. Soc. 356 (2004), 2557-2568
MSC (2000): Primary 03D25, 03D30; Secondary 03D35
Published electronically: February 27, 2004
MathSciNet review: 2052189
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that for any computably enumerable (c.e.) degree $\mathbf{w}$, if $\mathbf{w\not=0}$, then there is a c.e. degree $\mathbf{a}$ such that $\mathbf{(a\lor w)'} = \mathbf{a''}= \mathbf{0''}$ (so $\mathbf{a}$ is low$_2$and $\mathbf{a\lor w}$ is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low$_2$ c.e. degrees are not elementarily equivalent as partial orderings.

References [Enhancements On Off] (What's this?)

  • 1. M. Bickford and C. F. Mills,
    Lowness properties of r.e. degrees,
    Unpublished preprint, 1982.
  • 2. Peter Cholak, Marcia Groszek, and Theodore Slaman,
    An almost deep degree,
    J. Symbolic Logic, 66(2):881-901, 2001. MR 2002d:03070
  • 3. S. Barry Cooper,
    On a theorem of C. E. M. Yates,
    Handwritten notes, 1974.
  • 4. S. Barry Cooper and Angsheng Li,
    Splitting and nonsplitting, II: A low$_2$ c.e. degree above which $\mathbf{0'}$ is not splittable,
    J. Symbolic Logic, 67:1391-1430, 2002. MR 2003k:03055
  • 5. Steffen Lempp and Theodore A. Slaman,
    A limit on relative genericity in the recursively enumerable sets,
    J. Symbolic Logic, 54:376-395, 1989. MR 90f:03077
  • 6. Angsheng Li,
    Definable relations on the computably enumerable degrees,
    in Computability and Models, pages 267-288.
    edited by S. B. Cooper and S. S. Goncharov,
    Kluwer Academic / Plenum Publishers, New York, 2003.
  • 7. Angsheng Li,
    Elementary differences among jump hierarchies,
  • 8. André Nies, Richard A. Shore, and Theodore A. Slaman,
    Interpretability and definability in the recursively enumerable degrees,
    Proc. London Math. Soc. (3), 77(2):241-291, 1998. MR 99m:03083
  • 9. David B. Posner and Robert W. Robinson,
    Degrees joining to $\mathbf{0}\sp{\prime} $,
    J. Symbolic Logic, 46(4):714-722, 1981. MR 83c:03040
  • 10. Robert I. Soare,
    Recursively Enumerable Sets and Degrees,
    Springer-Verlag, Heidelberg, 1987. MR 88m:03003

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03D25, 03D30, 03D35

Retrieve articles in all journals with MSC (2000): 03D25, 03D30, 03D35

Additional Information

Carl G. Jockusch Jr.
Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green St., Urbana, Illinois 61801

Angsheng Li
Affiliation: Institute of Software, Chinese Academy of Sciences, P. O. Box 8718, Beijing, 100080, People’s Republic of China

Yue Yang
Affiliation: Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, Singapore 119260

Keywords: Join theorem, computably enumerable degree, definable ideals, Turing jump
Received by editor(s): June 11, 2002
Published electronically: February 27, 2004
Additional Notes: The first author was partially supported by NSF Grant DMS-98-03073. The second author was supported by EPSRC Research Grant no. GR/M 91419, “Turing Definability” (UK), by NSF Grant No. 69973048, by NSF Major Grant No. 19931020 (P. R. China), and by National Distinguished Young Investigator Award no. 60325206 (China). The third author was partially supported by the NSTB OAP programme and NUS Grant No. R-146-000-028-112 (Singapore). All three authors were partially supported by NSFC grant No. 60310213 “New Directions in Theory and Applications of Models of Computation" (China)
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society