Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A splitting theorem for $n-REA$ degrees

Authors: Richard A. Shore and Theodore A. Slaman
Journal: Proc. Amer. Math. Soc. 129 (2001), 3721-3728
MSC (2000): Primary 03D25, 03D30; Secondary 03D55
Published electronically: April 25, 2001
MathSciNet review: 1860508
Full-text PDF

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 [Enhancements On Off] (What's this?)

  • [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

Theodore A. Slaman
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840

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
Published electronically: 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.
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society