A splitting theorem for $n-REA$ degrees
HTML articles powered by AMS MathViewer
- by Richard A. Shore and Theodore A. Slaman PDF
- Proc. Amer. Math. Soc. 129 (2001), 3721-3728 Request permission
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
- S. Barry Cooper, The jump is definable in the structure of the degrees of unsolvability, Bull. Amer. Math. Soc. (N.S.) 23 (1990), no. 1, 151–158. MR 1027898, DOI 10.1090/S0273-0979-1990-15923-3
- Cooper, S. B., On a conjecture of Kleene and Post, Department of Pure Mathematics, Leeds University, 1993 Preprint Series No. 7.
- Cooper, S. B., The Turing definability of the relation of “computably enumerable in”, Computability Theory Seminar, University of Leeds.
- S. Barry Cooper and Richard L. Epstein, Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34 (1987), no. 1, 15–32. MR 887552, DOI 10.1016/0168-0072(87)90039-X
- Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620
- Edward R. Griffor (ed.), Handbook of computability theory, Studies in Logic and the Foundations of Mathematics, vol. 140, North-Holland Publishing Co., Amsterdam, 1999. MR 1721236
- Carl G. Jockusch Jr. and Richard A. Shore, Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic 49 (1984), no. 4, 1205–1236. MR 771789, DOI 10.2307/2274273
- Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, DOI 10.1016/0003-4843(76)90016-4
- Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
- Richard A. Shore, The structure of the degrees of unsolvability, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp. 33–51. MR 791051, DOI 10.1090/pspum/042/791051
- Richard A. Shore and Theodore A. Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), no. 5-6, 711–722. MR 1739227, DOI 10.4310/MRL.1999.v6.n6.a10
- Turing, A. M., Systems of logic based on ordinals, Proc. London Math. Soc. (3) 45, 161-228.
Additional Information
- Richard A. Shore
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 161135
- Email: shore@math.cornell.edu
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- 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.
- © Copyright 2001 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 129 (2001), 3721-3728
- MSC (2000): Primary 03D25, 03D30; Secondary 03D55
- DOI: https://doi.org/10.1090/S0002-9939-01-06015-4
- MathSciNet review: 1860508