Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
     

A splitting theorem for $n-REA$ degrees

Author(s): Richard A. Shore; Theodore A. Slaman
Journal: Proc. Amer. Math. Soc. 129 (2001), 3721-3728.
MSC (2000): Primary 03D25, 03D30; Secondary 03D55
Posted: April 25, 2001
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: We prove that, for any $D$, $A$ and $U$ with $D>_{T}A\oplus U$ and r.e., in $A\oplus U$, there are pairs $X_{0},X_{1}$ and $Y_{0},Y_{1}$ such that $D\equiv_{T}X_{0}\oplus X_{1}$; $D\equiv_{T}Y_{0}\oplus Y_{1}$; and, for any $i$ and $j$ from $\{0,1\}$ and any set $B$, if $X_{i}\oplus A\geq_{T}B$ and $Y_{j}\oplus A\geq_{T}B$, then $A\geq_{T}B$. We then deduce that for any degrees $\mathbf{d}$, $\mathbf{a}$, and $\mathbf{b}$ such that $\mathbf{a}$and $\mathbf{b}$ are recursive in $\mathbf{d}$, $\mathbf{a}\not \geq _{T}\mathbf{b}$, and $\mathbf{d}$ is $n-REA$ into $\mathbf{a}$, $\mathbf{d}$can be split over $\mathbf{a}$ avoiding $\mathbf{b}$. This shows that the Main Theorem of Cooper (Bull. Amer. Math. Soc. 23 (1990), 151-158) is false.


References:

[1990]
Cooper, S. B., The jump is definable in the structure of the degrees of unsolvability (research announcement), Bull. Amer. Math. Soc. 23, 151-158. MR 91e:03044

[1993]
Cooper, S. B., On a conjecture of Kleene and Post, Department of Pure Mathematics, Leeds University, 1993 Preprint Series No. 7.

[2000]
Cooper, S. B., The Turing definability of the relation of ``computably enumerable in'', Computability Theory Seminar, University of Leeds.

[1987]
Cooper, S. B. and Epstein, R. L., Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34, 15-32. MR 89f:03035

[1979]
Epstein, R., Degrees of Unsolvability: Structure and Theory, Lecture Notes in Mathematics 759, Springer-Verlag, Heidelberg. MR 81e:03042

[1999]
Griffor, E. (ed.), Handbook of Computability Theory, North-Holland, Amsterdam. MR 2000e:03001

[1984]
Jockusch, C. G. Jr. and Shore, R. A., Pseudo-jump operators II: transfinite iterations, hierarchies and minimal covers, J. Symb. Logic 49, 1205-1236. MR 86g:03072

[1976]
Lachlan, A., A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9, 307-365. MR 53:12912

[1963]
Sacks, G. E., On the degrees less than $\mathbf{0}^{\prime}$, Ann. of Math. (2) 77, 211-231. MR 26:3604

[1985]
Shore, R. A., The structure of the degrees of unsolvability, in Recursion theory, Proc. Symp. Pure Math. 42, A. Nerode and R. A. Shore eds., Amer. Math. Soc., Providence RI, 33-51. MR 87e:03100

[2000]
Shore, R. A. and Slaman, T. A., Defining the Turing jump, Math. Res. Lett. 6 (1999), 711-722. MR 2000m:03104

[1939]
Turing, A. M., Systems of logic based on ordinals, Proc. London Math. Soc. (3) 45, 161-228.

Similar Articles:

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

Retrieve articles in all Journals with MSC (2000): 03D25, 03D30, 03D55


Additional Information:

Richard A. Shore
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: shore@math.cornell.edu

Theodore A. Slaman
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840
Email: slaman@math.berkeley.edu

DOI: 10.1090/S0002-9939-01-06015-4
PII: S 0002-9939(01)06015-4
Keywords: Degrees, Turing degrees, recursively enumerable degrees, splitting theorems
Received by editor(s): November 15, 1999
Received by editor(s) in revised form: May 4, 2000
Posted: April 25, 2001
Additional Notes: The first author was partially supported by NSF Grant DMS-9802843.
The second author was partially supported by NSF Grant DMS-97-96121.
Communicated by: Carl G. Jockusch, Jr.
Copyright of article: Copyright 2001, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google