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), 27192736
MSC (1991):
Primary 03D25, 03D35
MathSciNet review:
1389784
Fulltext 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
AmbosSpies and Richard
A. Shore, Undecidability and 1types 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
(94g:03082), http://dx.doi.org/10.1016/01680072(93)90206S
 [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
(83i:03067), http://dx.doi.org/10.1090/S027309791982149709
 [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
(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]
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
(97a:03003)
 [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
(97f:03062), http://dx.doi.org/10.2307/2275877
 [Ni96]
A.
Nies, Undecidable fragments of elementary theories, Algebra
Universalis 35 (1996), no. 1, 8–33. MR 1360529
(96k:03099), http://dx.doi.org/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
(6,29f), http://dx.doi.org/10.1090/S000299041944081111
 [Sa63]
Gerald
E. Sacks, Degrees of unsolvability, Princeton University
Press, Princeton, N.J., 1963. MR 0186554
(32 #4013)
 [Sa64]
Gerald
E. Sacks, The recursively enumerable degrees are dense, Ann.
of Math. (2) 80 (1964), 300–312. MR 0166089
(29 #3367)
 [Sh65]
J.
R. Shoenfield, Applications of model theory to degrees of
unsolvability, Theory of Models (Proc. 1963 Internat. Sympos.
Berkeley), NorthHolland, Amsterdam, 1965, pp. 359–363. MR 0200154
(34 #53)
 [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, SpringerVerlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
 [Ya66]
C.
E. M. Yates, A minimal pair of recursively enumerable degrees,
J. Symbolic Logic 31 (1966), 159–168. MR 0205851
(34 #5677)
 [AS93]
 K. AmbosSpies and R. A. Shore, Undecidability and onetypes in the recursively enumerable degrees, Ann. Pure Appl. Logic 63 (1993), 337. MR 94g:03082
 [HS82]
 L. Harrington and S. Shelah, The undecidability of the recursively enumerable degrees, Bull. AMS (N. S.) 6 (1982), 7980. 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), 537569. 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. 185204. 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), 11181136. MR 97f:03062
 [Ni96]
 A. Nies, Undecidable fragments of elementary theories, Algebra Universalis 35 (1996), 833. MR 96k:03099
 [Po44]
 E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. AMS 50 (1944), 284316. 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), 300312. 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.), NorthHolland, Amsterdam, 1965, pp. 359363. 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, SpringerVerlag, Berlin, 1987. MR 88m:03003
 [Ya66]
 C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159168. 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 606371514
Email:
nies@math.uchicago.edu
Theodore A. Slaman
Affiliation:
Department of Mathematics, University of California, Berkeley, California 947200001
Email:
slaman@math.berkeley.edu
DOI:
http://dx.doi.org/10.1090/S0002994798018005
PII:
S 00029947(98)018005
Keywords:
(Computably,
recursively) enumerable degrees,
$\Pi _{3}$theory,
fragment of firstorder theory,
undecidability
Received by editor(s):
December 20, 1995
Additional Notes:
The first author’s research was partially supported by NSF Grants DMS9100114 and DMS9504474. The second author’s research was partially supported by NSF Grant DMS9500983. The third author’s research was partially supported by NSF Grant DMS9500878.
Article copyright:
© Copyright 1998 American Mathematical Society
