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)

 
 

 

Biinterpretability up to double jump in the degrees below $ \mathbf{0}^{\prime}$


Author: Richard A. Shore
Journal: Proc. Amer. Math. Soc. 142 (2014), 351-360
MSC (2010): Primary 03D28
DOI: https://doi.org/10.1090/S0002-9939-2013-11719-3
Published electronically: September 12, 2013
MathSciNet review: 3119208
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] Klaus Ambos-Spies, Decheng Ding, Wei Wang, and Liang Yu, Bounding non- $ {\rm GL}_2$ and R.E.A, J. Symbolic Logic 74 (2009), no. 3, 989-1000. MR 2548472 (2011c:03094), https://doi.org/10.2178/jsl/1245158095
  • [2] 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, https://doi.org/10.2178/jsl/1327068690
  • [3] 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 (electronic) (2004). MR 2130306 (2005m:03086), https://doi.org/10.1305/ndjfl/1091122498
  • [4] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741 (94e:03002)
  • [5] Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no. 1, 61-89. MR 568916 (81k:03040), https://doi.org/10.1016/0003-4843(80)90004-2
  • [6] 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 (99m:03083), https://doi.org/10.1112/S002461159800046X
  • [7] Richard A. Shore, The theory of the degrees below $ {\bf0}^{\prime } $, J. London Math. Soc. (2) 24 (1981), no. 1, 1-14. MR 623666 (83m:03051), https://doi.org/10.1112/jlms/s2-24.1.1
  • [8] Richard A. Shore, Finitely generated codings and the degrees r.e. in a degree $ {\bf d}$, Proc. Amer. Math. Soc. 84 (1982), no. 2, 256-263. MR 637179 (84g:03061), https://doi.org/10.2307/2043675
  • [9] Richard A. Shore, Defining jump classes in the degrees below $ {\bf0}'$, Proc. Amer. Math. Soc. 104 (1988), no. 1, 287-292. MR 958085 (89i:03084), https://doi.org/10.2307/2047504
  • [10] Richard A. Shore, Direct and local definitions of the Turing jump, J. Math. Log. 7 (2007), no. 2, 229-262. MR 2423951 (2009h:03052), https://doi.org/10.1142/S0219061307000676
  • [11] Shore, R. A., Lecture notes on the Turing degrees, AII Graduate Summer School in Logic, Singapore, 28 June - 23 July 2010, World Sci. Publ.
  • [12] Stephen G. Simpson, First-order theory of the degrees of recursive unsolvability, Ann. of Math. (2) 105 (1977), no. 1, 121-139. MR 0432435 (55 #5423)
  • [13] Theodore A. Slaman, Degree structures, Proceedings of the International Congress of Mathematicians, Vol. II (Kyoto, 1990) Math. Soc. Japan, Tokyo, 1991, pp. 303-316. MR 1159219 (93b:03074)
  • [14] 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 (2009k:03065), https://doi.org/10.1142/9789812794055_0002
  • [15] Theodore A. Slaman and W. Hugh Woodin, Definability in the Turing degrees, Illinois J. Math. 30 (1986), no. 2, 320-334. MR 840131 (87m:03061)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D28

Retrieve articles in all journals with MSC (2010): 03D28


Additional Information

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-2013-11719-3
Received by editor(s): December 27, 2011
Received by editor(s) in revised form: December 28, 2011, and February 26, 2012
Published electronically: September 12, 2013
Additional Notes: The author was partially supported by NSF Grants DMS-0852811 and DMS-11675, and as a Visiting Professor in the Department of Mathematics and the Institute for Mathematical Sciences at the National University of Singapore, with partial funding from the John Templeton Foundation.
Communicated by: Julia Knight
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society