Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

There is no degree invariant half-jump


Authors: Rodney G. Downey and Richard A. Shore
Journal: Proc. Amer. Math. Soc. 125 (1997), 3033-3037
MSC (1991): Primary 03D25, 03E60, 04A15; Secondary 03D30
DOI: https://doi.org/10.1090/S0002-9939-97-03915-4
MathSciNet review: 1401736
Full-text PDF

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 [Enhancements On Off] (What's this?)

  • 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: https://doi.org/10.1090/S0002-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
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society