Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Extensions of embeddings below computably enumerable degrees

Authors: Rod Downey, Noam Greenberg, Andrew Lewis and Antonio Montalbán
Journal: Trans. Amer. Math. Soc. 365 (2013), 2977-3018
MSC (2010): Primary 03D28; Secondary 03D25
Published electronically: December 13, 2012
MathSciNet review: 3034456
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Toward establishing the decidability of the two-quantifier theory of the $ \Delta ^0_2$ Turing degrees with join, we study extensions of embeddings of upper-semi-lattices into the initial segments of Turing degrees determined by computably enumerable sets, in particular, the degree of the halting set $ \boldsymbol {0}'$. We obtain a good deal of sufficient and necessary conditions.

References [Enhancements On Off] (What's this?)

  • [Coo89] S. B. Cooper, The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989), no. 2, 527-539. MR 997886 (91b:03071)
  • [Dow87] R. G. Downey, $ \Delta \sp 0\sb 2$ degrees and transfer theorems, Illinois J. Math. 31 (1987), no. 3, 419-427. MR 892177 (89c:03070)
  • [Eps79] Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620 (81e:03042)
  • [Fri57] Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236-238. MR 0084474 (18,867a)
  • [Joc80] Carl G. Jockusch, Jr., Degrees of generic sets, Recursion Theory: its Generalisation and Applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979), London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge, 1980, pp. 110-139. MR 83i:03070
  • [JS83] 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 (84c:03081)
  • [JS93] C.G. Jockusch Jr. and T.A. Slaman, On the $ \Sigma _2$ theory of the upper semilattice of the Turing degrees, Journal of Symbolic Logic 58 (1993), 193-204. MR 1217184 (94d:03084)
  • [KP54] S.C. Kleene and E.L. Post, The upper semi-lattice of the degrees of recursive unsolvability, Annals of Mathematics (2) 59 (1954), 379-407. MR 0061078 (15:772a)
  • [Ler83] M. Lerman, Degrees of unsolvability, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983. MR 708718 (85h:03044)
  • [Lew05] Andrew E. M. Lewis, The minimal complementation property above $ 0'$, MLQ Math. Log. Q. 51 (2005), no. 5, 470-492. MR 2163759 (2006d:03066)
  • [LL76] A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), no. 2, 289-300. MR 0403937 (53:7746)
  • [LS75] Richard E. Ladner and Leonard P. Sasso, Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429-448. MR 0379157 (52:63)
  • [LS88] Manuel Lerman and Richard A. Shore, Decidability and invariant classes for degree structures, Trans. Amer. Math. Soc. 310 (1988), no. 2, 669-692. MR 973174 (90c:03031)
  • [MNS04] Russell G. Miller, Andre O. Nies, and Richard A. Shore, The $ \forall \exists $-theory of $ {\mathcal R}(\leq ,\vee ,\wedge )$ is undecidable, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3025-3067 (electronic). MR 2052940 (2005g:03057)
  • [Mon] Antonio Montalbán, Embeddings into the Turing degrees, Lect. Notes Log., Vol. 32, Assoc. Symbol. Logic, Chicago, IL, 2009. MR 2562555 (2011d:03063)
  • [Muc56] A. A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR, N.S. 108 (1956), 194-197. MR 0081859 (18:457a)
  • [Pos77] David Posner, High degrees, Ph.D. thesis, University of California, Berkeley, 1977. MR 2627247
  • [PR81] D. B. Posner and R. W. Robinson, Degrees joining to $ \boldsymbol {0}\sp {\prime }$, J. Symbolic Logic 46 (1981), no. 4, 714-722. MR 83c:03040
  • [Rob72] R. W. Robinson, Degrees joining $ {\boldsymbol {0}'}$, Notices of the American Mathematical Society 19 (1972), A-615.
  • [Sac61] Gerald E. Sacks, A minimal degree less than $ \boldsymbol {0}'$, Bull. Amer. Math. Soc. 67 (1961), 416-419. MR 0126380 (23:A3676)
  • [Sac63] -, On the degrees less than $ \boldsymbol {0}'$, Ann. of Math. (2) 77 (1963), 211-231. MR 0146078 (26:3604)
  • [Sho59] J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644-653. MR 0105355 (21:4097)
  • [Sho81] Richard A. Shore, The theory of the degrees below $ \boldsymbol {0'}$, J. London Math. Soc. 24 (1981), 1-14. MR 623666 (83m:03051)
  • [Sho06] Richard A. Shore, Degree structures: Local and global investigations, Bulletin of Symbolic Logic 12 (2006), 369-389. MR 2248589 (2007e:03074)
  • [Soa87] Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, A study of computable functions and computably generated sets. MR 88m:03003
  • [SS89] T. A. Slaman and J. R. Steel, Complementation in the Turing degrees, J. Symbolic Logic 54 (1989), no. 1, 160-176. MR 90c:03034
  • [SS01] Theodore A. Slaman and Robert I. Soare, Extension of embeddings in the computably enumerable degrees, Ann. of Math. (2) 154 (2001), no. 1, 1-43. MR 1847587 (2002f:03079)

Similar Articles

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

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

Additional Information

Rod Downey
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand

Noam Greenberg
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University. P.O. Box 600, Wellington, New Zealand

Andrew Lewis
Affiliation: School of Mathematics, University of Leeds, Leeds, United Kingdom

Antonio Montalbán
Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637

Keywords: Turing degrees, decidability, extensions of embeddings
Received by editor(s): December 9, 2009
Received by editor(s) in revised form: June 30, 2011
Published electronically: December 13, 2012
Additional Notes: The first two authors were supported by the Marsden Fund of New Zealand.
The third author was supported by a Royal Society University Research Fellowship.
The fourth author was partially supported by NSF Grant DMS-0600824, and by the Marsden Fund of New Zealand via a postdoctoral fellowship.
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society