A splitting theorem for degrees
Authors:
Richard A. Shore and Theodore A. Slaman
Journal:
Proc. Amer. Math. Soc. 129 (2001), 37213728
MSC (2000):
Primary 03D25, 03D30; Secondary 03D55
Published electronically:
April 25, 2001
MathSciNet review:
1860508
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We prove that, for any , and with and r.e., in , there are pairs and such that ; ; and, for any and from and any set , if and , then . We then deduce that for any degrees , , and such that and are recursive in , , and is into , can be split over avoiding . This shows that the Main Theorem of Cooper (Bull. Amer. Math. Soc. 23 (1990), 151158) is false.
 [1990]
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
(91e:03044), http://dx.doi.org/10.1090/S027309791990159233
 [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]
S.
Barry Cooper and Richard
L. Epstein, Complementing below recursively enumerable
degrees, Ann. Pure Appl. Logic 34 (1987), no. 1,
15–32. MR
887552 (89f:03035), http://dx.doi.org/10.1016/01680072(87)90039X
 [1979]
Richard
L. Epstein, Degrees of unsolvability: structure and theory,
Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620
(81e:03042)
 [1999]
Edward
R. Griffor (ed.), Handbook of computability theory, Studies in
Logic and the Foundations of Mathematics, vol. 140, NorthHolland
Publishing Co., Amsterdam, 1999. MR 1721236
(2000e:03001)
 [1984]
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
(86g:03072), http://dx.doi.org/10.2307/2274273
 [1976]
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 0409150
(53 #12912)
 [1963]
Gerald
E. Sacks, On the degrees less than 0′, Ann. of Math. (2)
77 (1963), 211–231. MR 0146078
(26 #3604)
 [1985]
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
(87e:03100), http://dx.doi.org/10.1090/pspum/042/791051
 [2000]
Richard
A. Shore and Theodore
A. Slaman, Defining the Turing jump, Math. Res. Lett.
6 (1999), no. 56, 711–722. MR 1739227
(2000m:03104), http://dx.doi.org/10.4310/MRL.1999.v6.n6.a10
 [1939]
Turing, A. M., Systems of logic based on ordinals, Proc. London Math. Soc. (3) 45, 161228.
 [1990]
 Cooper, S. B., The jump is definable in the structure of the degrees of unsolvability (research announcement), Bull. Amer. Math. Soc. 23, 151158. 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, 1532. MR 89f:03035
 [1979]
 Epstein, R., Degrees of Unsolvability: Structure and Theory, Lecture Notes in Mathematics 759, SpringerVerlag, Heidelberg. MR 81e:03042
 [1999]
 Griffor, E. (ed.), Handbook of Computability Theory, NorthHolland, Amsterdam. MR 2000e:03001
 [1984]
 Jockusch, C. G. Jr. and Shore, R. A., Pseudojump operators II: transfinite iterations, hierarchies and minimal covers, J. Symb. Logic 49, 12051236. MR 86g:03072
 [1976]
 Lachlan, A., A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9, 307365. MR 53:12912
 [1963]
 Sacks, G. E., On the degrees less than , Ann. of Math. (2) 77, 211231. 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, 3351. MR 87e:03100
 [2000]
 Shore, R. A. and Slaman, T. A., Defining the Turing jump, Math. Res. Lett. 6 (1999), 711722. MR 2000m:03104
 [1939]
 Turing, A. M., Systems of logic based on ordinals, Proc. London Math. Soc. (3) 45, 161228.
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 947203840
Email:
slaman@math.berkeley.edu
DOI:
http://dx.doi.org/10.1090/S0002993901060154
PII:
S 00029939(01)060154
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 DMS9802843.
The second author was partially supported by NSF Grant DMS9796121.
Communicated by:
Carl G. Jockusch, Jr.
Article copyright:
© Copyright 2001
American Mathematical Society
