A join theorem for the computably enumerable degrees
HTML articles powered by AMS MathViewer
- by Carl G. Jockusch Jr., Angsheng Li and Yue Yang PDF
- Trans. Amer. Math. Soc. 356 (2004), 2557-2568 Request permission
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
- M. Bickford and C. F. Mills, Lowness properties of r.e. degrees, Unpublished preprint, 1982.
- Peter Cholak, Marcia Groszek, and Theodore Slaman, An almost deep degree, J. Symbolic Logic 66 (2001), no. 2, 881–901. MR 1833485, DOI 10.2307/2695051
- S. Barry Cooper, On a theorem of C. E. M. Yates, Handwritten notes, 1974.
- S. Barry Cooper and Angsheng Li, Splitting and nonsplitting. II. A low$_2$ C.E. degree about which ${\bf 0}’$ is not splittable, J. Symbolic Logic 67 (2002), no. 4, 1391–1430. MR 1955245, DOI 10.2178/jsl/1190150292
- Steffen Lempp and Theodore A. Slaman, A limit on relative genericity in the recursively enumerable sets, J. Symbolic Logic 54 (1989), no. 2, 376–395. MR 997873, DOI 10.2307/2274854
- 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.
- Angsheng Li, Elementary differences among jump hierarchies, preprint.
- André Nies, Richard A. Shore, and Theodore A. Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77 (1998), no. 2, 241–291. MR 1635141, DOI 10.1112/S002461159800046X
- David B. Posner and Robert W. Robinson, Degrees joining to ${\bf 0}^{\prime }$, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, DOI 10.2307/2273221
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Additional Information
- Carl G. Jockusch Jr.
- Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green St., Urbana, Illinois 61801
- Email: jockusch@math.uiuc.edu
- Angsheng Li
- Affiliation: Institute of Software, Chinese Academy of Sciences, P. O. Box 8718, Beijing, 100080, People’s Republic of China
- Email: angsheng@gcl.iscas.ac.cn
- Yue Yang
- Affiliation: Department of Mathematics, Faculty of Science, National University of Singapore, Lower Kent Ridge Road, Singapore 119260
- Email: matyangy@leonis.nus.edu.sg
- 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)
- © Copyright 2004 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 356 (2004), 2557-2568
- MSC (2000): Primary 03D25, 03D30; Secondary 03D35
- DOI: https://doi.org/10.1090/S0002-9947-04-03585-8
- MathSciNet review: 2052189