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)

 
 

 

The $\Pi _{3}$-theory of the computably enumerable
Turing degrees is undecidable


Authors: Steffen Lempp, André Nies and Theodore A. Slaman
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show the undecidability of the $\Pi _{3}$-theory of the partial order of computably enumerable Turing degrees.


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

  • [AS93] K. Ambos-Spies and R. A. Shore, Undecidability and one-types in the recursively enumerable degrees, Ann. Pure Appl. Logic 63 (1993), 3-37. MR 94g:03082
  • [HS82] L. Harrington and S. Shelah, The undecidability of the recursively enumerable degrees, Bull. AMS (N. S.) 6 (1982), 79-80. MR 83i:03067
  • [HSta] L. Harrington and T.A. Slaman, unpublished.
  • [La66] A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537-569. MR 34:4126
  • [LLta] 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).
  • [Le96] M. Lerman, Embeddings into the recursively enumerable degrees, Computability, Enumerability, Unsolvability: Directions in Recursion Theory (S. B. Cooper et al., eds.), London Math. Soc. Lecture Note Ser., no. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 185-204. MR 97a:03003
  • [LNi95] S. Lempp, A. Nies, The undecidability of the $\Pi _{4}$-theory of the r.e. wtt and Turing degrees, J. Symbolic Logic 60 (1995), 1118-1136. MR 97f:03062
  • [Ni96] A. Nies, Undecidable fragments of elementary theories, Algebra Universalis 35 (1996), 8-33. MR 96k:03099
  • [Po44] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. AMS 50 (1944), 284-316. MR 6:29f
  • [Sa63] G. E. Sacks, Degrees of unsolvability, Ann. of Math. Studies No. 55, Princeton University Press, Princeton, N.J., 1963. MR 32:4013
  • [Sa64] G. E. Sacks, The recursively enumerable degrees are dense, Annals of Math. (2) 80 (1964), 300-312. MR 29:3367
  • [Sh65] J. R. Shoenfield, Application of model theory to degrees of unsolvability, Symposium on the Theory of Models (J. Addison, L. Henkin, A. Tarski, eds.), North-Holland, Amsterdam, 1965, pp. 359-363. MR 34:53
  • [SSta] T. A. Slaman and R. I. Soare, Extension of embeddings in the computably enumerable degrees (to appear).
  • [So87] R. I. Soare, Recursively Enumerable Sets and Degrees: The Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, $\Omega $-Series, Springer-Verlag, Berlin, 1987. MR 88m:03003
  • [Ya66] C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159-168. MR 34:5677

Similar Articles

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

Retrieve articles in all journals with MSC (1991): 03D25, 03D35


Additional Information

Steffen Lempp
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706–1388
Email: lempp@math.wisc.edu

André Nies
Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637-1514
Email: nies@math.uchicago.edu

Theodore A. Slaman
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-0001
Email: slaman@math.berkeley.edu

DOI: https://doi.org/10.1090/S0002-9947-98-01800-5
Keywords: (Computably, recursively) enumerable degrees, $\Pi _{3}$-theory, fragment of first-order theory, undecidability
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.
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society