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

MathSciNet review:
1389784

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

**[AS93]**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**, 10.1016/0168-0072(93)90206-S**[HS82]**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**, 10.1090/S0273-0979-1982-14970-9**[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**0204282****[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]**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****[LNi95]**Steffen Lempp and André Nies,*The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees*, J. Symbolic Logic**60**(1995), no. 4, 1118–1136. MR**1367199**, 10.2307/2275877**[Ni96]**A. Nies,*Undecidable fragments of elementary theories*, Algebra Universalis**35**(1996), no. 1, 8–33. MR**1360529**, 10.1007/BF01190967**[Po44]**Emil L. Post,*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284–316. MR**0010514**, 10.1090/S0002-9904-1944-08111-1**[Sa63]**Gerald E. Sacks,*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554****[Sa64]**Gerald E. Sacks,*The recursively enumerable degrees are dense*, Ann. of Math. (2)**80**(1964), 300–312. MR**0166089****[Sh65]**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****[SSta]**T. A. Slaman and R. I. Soare,*Extension of embeddings in the computably enumerable degrees*(to appear).**[So87]**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****[Ya66]**C. E. M. Yates,*A minimal pair of recursively enumerable degrees*, J. Symbolic Logic**31**(1966), 159–168. MR**0205851**

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:
http://dx.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