The $\Delta ^0_2$ Turing degrees: Automorphisms and Definability
HTML articles powered by AMS MathViewer
- by Theodore A. Slaman and Mariya I. Soskova PDF
- Trans. Amer. Math. Soc. 370 (2018), 1351-1375 Request permission
Abstract:
We prove that the $\Delta ^0_2$ Turing degrees have a finite automorphism base. We apply this result to show that the automorphism group of ${\mathcal D}_T(\leq \mathbf {0’})$ is countable and that all its members have arithmetic presentations. We prove that every relation on ${\mathcal D}_T(\leq \mathbf {0’})$ induced by an arithmetically definable degree invariant relation is definable with finitely many $\Delta ^0_2$ parameters and show that rigidity for ${\mathcal D}_T(\leq \mathbf {0’})$ is equivalent to its biinterpretability with first order arithmetic.References
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- André Nies, Richard A. Shore, and Theodore A. Slaman, Definability in the recursively enumerable degrees, Bull. Symbolic Logic 2 (1996), no. 4, 392–404. MR 1460314, DOI 10.2307/421171
- Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
- Richard A. Shore, The theory of the degrees below ${\bf 0}^{\prime }$, J. London Math. Soc. (2) 24 (1981), no. 1, 1–14. MR 623666, DOI 10.1112/jlms/s2-24.1.1
- Richard A. Shore, Biinterpretability up to double jump in the degrees below $0’$, Proc. Amer. Math. Soc. 142 (2014), no. 1, 351–360. MR 3119208, DOI 10.1090/S0002-9939-2013-11719-3
- Stephen G. Simpson, First-order theory of the degrees of recursive unsolvability, Ann. of Math. (2) 105 (1977), no. 1, 121–139. MR 432435, DOI 10.2307/1971028
- T. A. Slaman and W. H. Woodin, Definability in degree structures, preprint, available at http://math.berkeley.edu/~slaman/talks/sw.pdf, 2005.
- Theodore A. Slaman and Mariya I. Soskova, The enumeration degrees: Local and global structural interactions, Accepted in Foundations of Mathematics. Essays for W. Hugh Woodin on the occasion of his 60th Birthday, A. Caicedo, J. Cummings, P. Koellner and P. Larson, editors, AMS Contemporary Mathematics .
- Theodore A. Slaman and W. Hugh Woodin, Definability in the Turing degrees, Illinois J. Math. 30 (1986), no. 2, 320–334. MR 840131
- Lawrence Vaughn Welch, A HIERARCHY OF FAMILIES OF RECURSIVELY ENUMERABLE DEGREES AND A THEOREM ON BOUNDING MINIMAL PAIRS, ProQuest LLC, Ann Arbor, MI, 1981. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR 2631544
Additional Information
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720-3840
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- Mariya I. Soskova
- Affiliation: Faculty of Mathematics and Informatics, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria
- Address at time of publication: Department of Mathematics, University of Wisconsin, Madison, 480 Lincoln Drive, Madison, Wisconsin 53706
- MR Author ID: 802392
- Email: msoskova@math.wisc.edu
- Received by editor(s): November 6, 2015
- Received by editor(s) in revised form: December 8, 2016
- Published electronically: October 18, 2017
- Additional Notes: The first author was partially supported by National Science Foundation grant number DMS-1301659. The second author was partially supported by an FP7-MC-IOF grant STRIDE (298471), the L’Oréal-UNESCO program “For women in science” and by the Sofia University Science Fund
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 370 (2018), 1351-1375
- MSC (2010): Primary 03D28
- DOI: https://doi.org/10.1090/tran/7187
- MathSciNet review: 3729503