|
The  -theory of the computably enumerable Turing degrees is undecidable
Author(s):
Steffen
Lempp;
André
Nies;
Theodore
A.
Slaman
Journal:
Trans. Amer. Math. Soc.
350
(1998),
2719-2736.
MSC (1991):
Primary 03D25, 03D35
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We show the undecidability of the  -theory of the partial order of computably enumerable Turing degrees.
References:
- [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
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:
10.1090/S0002-9947-98-01800-5
PII:
S 0002-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.
Copyright of article:
Copyright
1998,
American Mathematical Society
|
Comments: webmaster@ams.org