|
A splitting theorem for 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 , 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), 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
, 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
|