Extensions of embeddings below computably enumerable degrees

Downey, Rod; Greenberg, Noam; Lewis, Andrew; Montalbán, Antonio

doi:10.1090/S0002-9947-2012-05660-1

Extensions of embeddings below computably enumerable degrees
HTML articles powered by AMS MathViewer

by Rod Downey, Noam Greenberg, Andrew Lewis and Antonio Montalbán PDF

Trans. Amer. Math. Soc. 365 (2013), 2977-3018 Request permission

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

S. B. Cooper, The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989), no. 2, 527–539. MR 997886, DOI 10.2307/2274867
R. G. Downey, $\Delta ^0_2$ degrees and transfer theorems, Illinois J. Math. 31 (1987), no. 3, 419–427. MR 892177, DOI 10.1215/ijm/1256069291
Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620, DOI 10.1007/BFb0067135
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 84474, DOI 10.1073/pnas.43.2.236
Olga Taussky, An algebraic property of Laplace’s differential equation, Quart. J. Math. Oxford Ser. 10 (1939), 99–103. MR 83, DOI 10.1093/qmath/os-10.1.99
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
Carl G. Jockusch Jr. and Theodore A. Slaman, On the $\Sigma _2$-theory of the upper semilattice of Turing degrees, J. Symbolic Logic 58 (1993), no. 1, 193–204. MR 1217184, DOI 10.2307/2275332
S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
Andrew E. M. Lewis, The minimal complementation property above $0’$, MLQ Math. Log. Q. 51 (2005), no. 5, 470–492. MR 2163759, DOI 10.1002/malq.200410044
A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), no. 2, 289–300. MR 403937, DOI 10.2307/2272227
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 379157, DOI 10.1016/0003-4843(75)90007-8
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, DOI 10.1090/S0002-9947-1988-0973174-0
Russell G. Miller, Andre O. Nies, and Richard A. Shore, The $\forall \exists$-theory of $\scr R(\leq ,\vee ,\wedge )$ is undecidable, Trans. Amer. Math. Soc. 356 (2004), no. 8, 3025–3067. MR 2052940, DOI 10.1090/S0002-9947-03-03406-8
Antonio Montalban, Embeddings into the Turing degrees, Logic Colloquium 2006, Lect. Notes Log., vol. 32, Assoc. Symbol. Logic, Chicago, IL, 2009, pp. 229–246. MR 2562555, DOI 10.1017/CBO9780511605321.012
A. A. Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR (N.S.) 108 (1956), 194–197 (Russian). MR 0081859
David Barnett Posner, HIGH DEGREES, ProQuest LLC, Ann Arbor, MI, 1977. Thesis (Ph.D.)–University of California, Berkeley. MR 2627247
Olga Taussky, An algebraic property of Laplace’s differential equation, Quart. J. Math. Oxford Ser. 10 (1939), 99–103. MR 83, DOI 10.1093/qmath/os-10.1.99
R. W. Robinson, Degrees joining ${\boldsymbol {0}’}$, Notices of the American Mathematical Society 19 (1972), A–615.
Gerald E. Sacks, A minimal degree less than $0’$, Bull. Amer. Math. Soc. 67 (1961), 416–419. MR 126380, DOI 10.1090/S0002-9904-1961-10652-6
Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, DOI 10.2307/1970028
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, Degree structures: local and global investigations, Bull. Symbolic Logic 12 (2006), no. 3, 369–389. MR 2248589, DOI 10.2178/bsl/1154698739
S. Minakshi Sundaram, On non-linear partial differential equations of the parabolic type, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 479–494. MR 0000088, DOI 10.1007/BF03046993
John W. Green, Harmonic functions in domains with multiple boundary points, Amer. J. Math. 61 (1939), 609–632. MR 90, DOI 10.2307/2371316
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, DOI 10.2307/3062109