Biinterpretability up to double jump in the degrees below 0′

Shore, Richard

doi:10.1090/S0002-9939-2013-11719-3

Biinterpretability up to double jump in the degrees below $\mathbf {0}^{\prime }$
HTML articles powered by AMS MathViewer

by Richard A. Shore PDF

Proc. Amer. Math. Soc. 142 (2014), 351-360 Request permission

Abstract:

We prove that for every $\mathbf {z\leq 0}^{\prime }$ with $\mathbf {z}^{\prime \prime }>\mathbf {0}^{\prime \prime }$ (i.e. $\mathbf {z\in \bar {L}}_{2}$), the structure $\mathcal {D}(\leq \mathbf {z})$ of the Turing degrees below $\mathbf {x}$ is biinterpretable with first order arithmetic up to double jump. As a corollary, every relation on $\mathcal {D}(\leq \mathbf {z})$ which is invariant under double jump is definable in $\mathcal {D}(\leq \mathbf {z})$ if and only if it is definable in arithmetic.

References

Klaus Ambos-Spies, Decheng Ding, Wei Wang, and Liang Yu, Bounding non-$\textrm {GL}_2$ and R.E.A, J. Symbolic Logic 74 (2009), no. 3, 989–1000. MR 2548472, DOI 10.2178/jsl/1245158095
Mingzhong Cai and Richard A. Shore, Domination, forcing, array nonrecursiveness and relative recursive enumerability, J. Symbolic Logic 77 (2012), no. 1, 33–48. MR 2951628, DOI 10.2178/jsl/1327068690
Noam Greenberg and Antonio Montalbán, Embedding and coding below a 1-generic degree, Notre Dame J. Formal Logic 44 (2003), no. 4, 200–216 (2004). MR 2130306, DOI 10.1305/ndjfl/1091122498
Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no. 1, 61–89. MR 568916, DOI 10.1016/0003-4843(80)90004-2
André Nies, Richard A. Shore, and Theodore A. Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77 (1998), no. 2, 241–291. MR 1635141, DOI 10.1112/S002461159800046X
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, Finitely generated codings and the degrees r.e. in a degree $\textbf {d}$, Proc. Amer. Math. Soc. 84 (1982), no. 2, 256–263. MR 637179, DOI 10.1090/S0002-9939-1982-0637179-1
Richard A. Shore, Defining jump classes in the degrees below ${\bf 0}’$, Proc. Amer. Math. Soc. 104 (1988), no. 1, 287–292. MR 958085, DOI 10.1090/S0002-9939-1988-0958085-4
Richard A. Shore, Direct and local definitions of the Turing jump, J. Math. Log. 7 (2007), no. 2, 229–262. MR 2423951, DOI 10.1142/S0219061307000676
Shore, R. A., Lecture notes on the Turing degrees, AII Graduate Summer School in Logic, Singapore, 28 June - 23 July 2010, World Sci. Publ.
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
Theodore A. Slaman, Degree structures, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990) Math. Soc. Japan, Tokyo, 1991, pp. 303–316. MR 1159219
Theodore A. Slaman, Global properties of the Turing degrees and the Turing jump, Computational prospects of infinity. Part I. Tutorials, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 14, World Sci. Publ., Hackensack, NJ, 2008, pp. 83–101. MR 2449478, DOI 10.1142/9789812794055_{0}002
Theodore A. Slaman and W. Hugh Woodin, Definability in the Turing degrees, Illinois J. Math. 30 (1986), no. 2, 320–334. MR 840131