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
Additional Information
- Rod Downey
- Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
- MR Author ID: 59535
- Email: Rod.Downey@msor.vuw.ac.nz
- Noam Greenberg
- Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University. P.O. Box 600, Wellington, New Zealand
- MR Author ID: 757288
- ORCID: 0000-0003-2917-3848
- Email: greenberg@msor.vuw.ac.nz
- Andrew Lewis
- Affiliation: School of Mathematics, University of Leeds, Leeds, United Kingdom
- MR Author ID: 748032
- Email: andy@aemlewis.co.uk
- Antonio Montalbán
- Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637
- Email: antonio@math.uchicago.edu
- 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. - © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 365 (2013), 2977-3018
- MSC (2010): Primary 03D28; Secondary 03D25
- DOI: https://doi.org/10.1090/S0002-9947-2012-05660-1
- MathSciNet review: 3034456