The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
HTML articles powered by AMS MathViewer
- by Steffen Lempp, André Nies and Theodore A. Slaman PDF
- Trans. Amer. Math. Soc. 350 (1998), 2719-2736 Request permission
Abstract:
We show the undecidability of the $\Pi _{3}$-theory of the partial order of computably enumerable Turing degrees.References
- Klaus Ambos-Spies and Richard A. Shore, Undecidability and $1$-types in the recursively enumerable degrees, Ann. Pure Appl. Logic 63 (1993), no. 1, 3–37. 9th International Congress of Logic, Methodology and Philosophy of Science (Uppsala, 1991). MR 1238106, DOI 10.1016/0168-0072(93)90206-S
- Leo Harrington and Saharon Shelah, The undecidability of the recursively enumerable degrees, Bull. Amer. Math. Soc. (N.S.) 6 (1982), no. 1, 79–80. MR 634436, DOI 10.1090/S0273-0979-1982-14970-9
- L. Harrington and T.A. Slaman, unpublished.
- A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
- S. Lempp and M. Lerman, A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees, Ann. Pure Appl. Logic (to appear).
- S. B. Cooper, T. A. Slaman, and S. S. Wainer (eds.), Computability, enumerability, unsolvability, London Mathematical Society Lecture Note Series, vol. 224, Cambridge University Press, Cambridge, 1996. Directions in recursion theory. MR 1395872, DOI 10.1017/CBO9780511629167
- Steffen Lempp and André Nies, The undecidability of the $\Pi _4$-theory for the r.e. wtt and Turing degrees, J. Symbolic Logic 60 (1995), no. 4, 1118–1136. MR 1367199, DOI 10.2307/2275877
- A. Nies, Undecidable fragments of elementary theories, Algebra Universalis 35 (1996), no. 1, 8–33. MR 1360529, DOI 10.1007/BF01190967
- Albert Eagle, Series for all the roots of the equation $(z-a)^m=k(z-b)^n$, Amer. Math. Monthly 46 (1939), 425–428. MR 6, DOI 10.2307/2303037
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Gerald E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312. MR 166089, DOI 10.2307/1970393
- J. R. Shoenfield, Applications of model theory to degrees of unsolvability, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 359–363. MR 0200154
- T. A. Slaman and R. I. Soare, Extension of embeddings in the computably enumerable degrees (to appear).
- 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 882921, DOI 10.1007/978-3-662-02460-7
- C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807
Additional Information
- Steffen Lempp
- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706–1388
- MR Author ID: 247988
- Email: lempp@math.wisc.edu
- André Nies
- Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637-1514
- MR Author ID: 328692
- Email: nies@math.uchicago.edu
- Theodore A. Slaman
- Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-0001
- MR Author ID: 163530
- Email: slaman@math.berkeley.edu
- Received by editor(s): December 20, 1995
- Additional Notes: The first author’s research was partially supported by NSF Grants DMS-9100114 and DMS-9504474. The second author’s research was partially supported by NSF Grant DMS-9500983. The third author’s research was partially supported by NSF Grant DMS-9500878.
- © Copyright 1998 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 350 (1998), 2719-2736
- MSC (1991): Primary 03D25, 03D35
- DOI: https://doi.org/10.1090/S0002-9947-98-01800-5
- MathSciNet review: 1389784