The -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

Abstract | References | Similar Articles | Additional Information

Abstract: We show the undecidability of the -theory of the partial order of computably enumerable Turing degrees.

**[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 -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, -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**

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