|
A join theorem for the computably enumerable degrees
Author(s):
Carl
G.
Jockusch Jr.;
Angsheng
Li;
Yue
Yang
Journal:
Trans. Amer. Math. Soc.
356
(2004),
2557-2568.
MSC (2000):
Primary 03D25, 03D30;
Secondary 03D35
Posted:
February 27, 2004
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
It is shown that for any computably enumerable (c.e.) degree  , if  , then there is a c.e. degree  such that  (so  is low and  is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low c.e. degrees are not elementarily equivalent as partial orderings.
References:
-
- 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 c.e. degree above which  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,
preprint. - 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  ,
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
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
DOI:
10.1090/S0002-9947-04-03585-8
PII:
S 0002-9947(04)03585-8
Keywords:
Join theorem,
computably enumerable degree,
definable ideals,
Turing jump
Received by editor(s):
June 11, 2002
Posted:
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 of article:
Copyright
2004,
American Mathematical Society
|
Comments: webmaster@ams.org