|
There is no degree invariant half-jump
Author(s):
Rodney
G.
Downey;
Richard
A.
Shore
Journal:
Proc. Amer. Math. Soc.
125
(1997),
3033-3037.
MSC (1991):
Primary 03D25, 03E60, 04A15;
Secondary 03D30
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We prove that there is no degree invariant solution to Post's problem that always gives an intermediate degree. In fact, assuming definable determinacy, if is any definable operator on degrees such that on a cone then is low or high on a cone of degrees, i.e., there is a degree such that for every or for every .
References:
- 1.
- Becker, H., A. characterization of jump operators, Journal of Symbolic Logic 53 (1988), 708-728. MR 90a:03067
- 2.
- Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Ac. Sci. 43 (1957), 236-238. MR 18:867a
- 3.
- Jockusch, C. G. Jr. and Shore, R. A., Pseudo-jump operators I: the r.e. case, Trans. Am. Math. Soc. 275 (1983), 599-609. MR 84c:03081
- 4.
- Kechris, A. S., The structure of Borel equivalence relations in Polish spaces, in Set Theory and the Continuum, H. Judah, W. Just and W. H. Woodin eds., MSRI Publications 26, Springer-Verlag, Berlin, 1992. MR 94h:03093
- 5.
- Kechris, A. S. and Y. Moschovakis, eds., Cabal Seminar 76-77, LNMS 689, Springer-Verlag, Berlin, 1978. MR 80b:03004
- 6.
- Lachlan, A. H., Uniform enumeration operators, Journal of Symbolic Logic 40 (1975), 401-409. MR 52:62
- 7.
- Martin, D. A., The axiom of determinacy and reduction principles in the analytic hierarchy, Bull. Am. Math. Soc. 74 (1968), 687-689. MR 37:2607
- 8.
- Martin, D. A., Borel determinacy, Ann. Math. (2) 102 (1975), 363-371. MR 53:7785
- 9.
- Muchnik, A. A., On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR N. S. 108 (1956), 29-32.
- 10.
- Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bull. Am. Math. Soc. 50 (1944), 84-316 MR 6:29f
- 11.
- Sacks, G. E., Degrees of unsolvability, Annals of Math. Studies 55, Princeton University Press, Princeton NJ 1963; 2
ed. 1966. MR 32:4013 - 12.
- Slaman, T. and J. R. Steel, Definable functions on degrees, in Cabal Seminar 81-85, A. S. Kechris, D. A. Martin and J.. R. Steel eds., LNMS 1333 (1988) Springer-Verlag, Berlin, 37-55. MR 89m:03033
- 13.
- Steel, J. R., A classification of jump operators, Journal of Symbolic Logic 47 (1982), 347-358. MR 84i:03085
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical Society
with MSC
(1991):
03D25, 03E60, 04A15,
03D30
Retrieve articles in all Journals with MSC
(1991):
03D25, 03E60, 04A15,
03D30
Additional Information:
Rodney
G.
Downey
Affiliation:
Department of Mathematics, Victoria University of Wellington, P. O. Box 600, Wellington, New Zealand
Email:
rod.downey@vuw.ac.nz
Richard
A.
Shore
Affiliation:
Department of Mathematics, Cornell University, Ithaca, New York 14853
Email:
shore@math.cornell.edu
DOI:
10.1090/S0002-9939-97-03915-4
PII:
S 0002-9939(97)03915-4
Keywords:
Post's problem,
degree invariant operators,
recursively enumerable degrees,
computably enumerable degrees,
Martin's conjecture,
axiom of determinacy
Received by editor(s):
February 16, 1996
Received by editor(s) in revised form:
May 9, 1996
Additional Notes:
The first author's research was partially supported by the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell University Contract DAAL03-91-C-0027, the IGC of Victoria University and the Marsden Fund for Basic Science under grant VIC-509.
The second author's research was partially supported by NSF Grant DMS-9503503 and the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell University Contract DAAL03-91-C-0027.
Communicated by:
Andreas R. Blass
Copyright of article:
Copyright
1997,
American Mathematical Society
|