There is no degree invariant half-jump
HTML articles powered by AMS MathViewer
- by Rodney G. Downey and Richard A. Shore PDF
- Proc. Amer. Math. Soc. 125 (1997), 3033-3037 Request permission
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}’$ 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})'' = \mathbf {a}''$ for every $\mathbf {a} \geq \mathbf {c}$ or $W(\mathbf {a})'' = \mathbf {a}''’$ for every $\mathbf {a} \geq \mathbf {c}$.References
- Howard Becker, A characterization of jump operators, J. Symbolic Logic 53 (1988), no. 3, 708–728. MR 960994, DOI 10.2307/2274567
- Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
- Carl G. Jockusch Jr. and Richard A. Shore, Pseudojump operators. I. The r.e. case, Trans. Amer. Math. Soc. 275 (1983), no. 2, 599–609. MR 682720, DOI 10.1090/S0002-9947-1983-0682720-1
- Alexander S. Kechris, The structure of Borel equivalence relations in Polish spaces, Set theory of the continuum (Berkeley, CA, 1989) Math. Sci. Res. Inst. Publ., vol. 26, Springer, New York, 1992, pp. 89–102. MR 1233813, DOI 10.1007/978-1-4613-9754-0_{7}
- Alexander S. Kechris and Yiannis N. Moschovakis (eds.), Cabal Seminar 76–77, Lecture Notes in Mathematics, vol. 689, Springer, Berlin, 1978. MR 526912
- A. H. Lachlan, Uniform enumeration operations, J. Symbolic Logic 40 (1975), no. 3, 401–409. MR 379156, DOI 10.2307/2272164
- Donald A. Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bull. Amer. Math. Soc. 74 (1968), 687–689. MR 227022, DOI 10.1090/S0002-9904-1968-11995-0
- Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
- 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.
- Albert Eagle, Series for all the roots of the equation $(z-a)^m=k(z-b)^n$, Amer. Math. Monthly 46 (1939), 425–428. MR 6, DOI 10.2307/2303037
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Theodore A. Slaman and John R. Steel, Definable functions on degrees, Cabal Seminar 81–85, Lecture Notes in Math., vol. 1333, Springer, Berlin, 1988, pp. 37–55. MR 960895, DOI 10.1007/BFb0084969
- John R. Steel, A classification of jump operators, J. Symbolic Logic 47 (1982), no. 2, 347–358. MR 654792, DOI 10.2307/2273146
Additional Information
- Rodney G. Downey
- Affiliation: Department of Mathematics, Victoria University of Wellington, P. O. Box 600, Wellington, New Zealand
- MR Author ID: 59535
- Email: rod.downey@vuw.ac.nz
- Richard A. Shore
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 161135
- Email: shore@math.cornell.edu
- 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 1997 American Mathematical Society
- 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