Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
     

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 $W$ is any definable operator on degrees such that ${\mathbf a<}W({\mathbf a)<{\mathbf a}}^{\prime }$ on a cone then $W$ is low$_2$ or high$_2$ on a cone of degrees, i.e., there is a degree ${\mathbf c}$ such that $W({\mathbf a)}^{\prime \prime }={\mathbf a}^{\prime \prime }$ for every ${\mathbf a\geq  {\mathbf c}}$ or $W({\mathbf a)}^{\prime \prime }={\mathbf a}^{\prime \prime \prime }$ for every ${\mathbf a\geq {\mathbf c}}$.


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$^{nd}$ 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


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google