Transactions of the American Mathematical Society

Author(s): Russell G. Miller; Andre O. Nies; Richard A. Shore
Journal: Trans. Amer. Math. Soc. 356 (2004), 3025-3067.
MSC (2000): Primary 03D25, 03D35; Secondary 03D28
Posted: October 8, 2003
Retrieve article in: PDF

Abstract: The three quantifier theory of $(\mathcal{R},\leq_{T})$ , the recursively enumerable degrees under Turing reducibility, was proven undecidable by Lempp, Nies and Slaman (1998). The two quantifier theory includes the lattice embedding problem and its decidability is a long-standing open question. A negative solution to this problem seems out of reach of the standard methods of interpretation of theories because the language is relational. We prove the undecidability of a fragment of the theory of $\mathcal{R}$ that lies between the two and three quantifier theories with $\leq_{T}$ but includes function symbols.

Theorem. The two quantifier theory of $(\mathcal{R},\leq ,\vee,\wedge)$ , the r.e. degrees with Turing reducibility, supremum and infimum (taken to be any total function extending the infimum relation on $\mathcal{R}$ ) is undecidable.

The same result holds for various lattices of ideals of $\mathcal{R}$ which are natural extensions of $\mathcal{R}$ preserving join and infimum when it exits.

[1928]

Bernays, P. and Schoenfikel, M. [1928], Zum Entscheidungsproblem der mathematischen Logik, Math. Ann. 99, 342-372.

[1997]

Börger, E., Grädel, E. and Gurevich, Y. [1997], The Classical Decision Problem, Springer, Berlin. MR 99b:03004

[1993]

Calhoun, W. C. [1993], Incomparable prime ideals of recursively enumerable degrees, 9th International Congress of Logic, Methodology and Philosophy of Science (Uppsala, 1991), Ann. Pure Appl. Logic 63, 39-56. MR 94g:03083

[2001]

Calhoun, W. C. and Lerman, M. [2001], Embedding finite lattices into the ideals of computably enumerable Turing degrees, J. Symbolic Logic 66, 1791-1802. MR 2002m:03059

[1979]

Dreben, B. and Goldfarb, W. [1979], The decision problem, Solvable Classes of Quantificational Formulas, Addison-Wesley, Reading, MA. MR 81i:03015

[1979]

Epstein, R. L. [1979], Degrees of Unsolvability: Structure and Theory, LNM 759, Springer-Verlag, Berlin. MR 81e:03042

[1957]

Friedberg, R. M. [1957], Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Ac. Sci. 43, 236-238. MR 18:867a

[1982]

Harrington, L. and Shelah, S. [1982], The undecidability of the recursively enumerable degrees (research announcement), Bull. Am. Math. Soc., N. S. 6, 79-80. MR 83i:03067

[1993]

Jockusch, C. G. Jr. and Slaman, T. A. [1993], On the $\Sigma\sb 2$ -theory of the upper semilattice of Turing degrees, J. Symbolic Logic 58, no. 1,

193-204. MR 94d:03084

[1954]

Kleene, S. C. and Post, E. L. [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379-407. MR 15:772a

[1966]

Lachlan, A. H. [1966], The impossibility of finding relative complements for recursively enumerable degrees, J. Symb. Logic 31, 434-454. MR 34:5673

[1968]

Lachlan, A. H. [1968], Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14, 457-472. MR 38:5620

[1975]

Lachlan, A. H. [1975], A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9, 307-365. MR 53:12912

[1998]

Lempp, S., Nies, A. and Slaman, T. A. [1998], The $\Pi_{3}$ -theory of the computably enumerable Turing degrees is undecidable, Trans. Am. Math. Soc. 350, 2719-2736. MR 98j:03056

[1971]

Lerman, M. [1971], Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93, 365-389. MR 46:7008

[1973]

Lerman, M. [1973], Admissible ordinals and priority arguments, in Cambridge Summer School in Mathematical Logic, LNM 337, A. R. D. Mathias and H. Rogers Jr. eds., Springer-Verlag, Berlin, 311-344. MR 52:59

[1983]

Lerman, M. [1983], Degrees of Unsolvability, Springer-Verlag, Berlin. MR 85h:03044

[2000]

Lerman, M. [2000], A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees, Annals of Pure and Applied Logic 101, 275-297. MR 2001g:03074

[1988]

Lerman, M. and Shore, R. A. [1988], Decidability and invariant classes for degree structures, Trans. Am. Math. Soc. 310, 669-692. MR 90c:03031

[1984]

Lerman, M., Shore, R. A. and Soare, R. I. [1984], The Elementary Theory of the Recursively Enumerable Degrees is not $\aleph_{0}$ -categorical, Advances in Mathematics 53, 301-320. MR 86d:03040

[1961]

Minsky, M. L. [1961], Recursive unsolvability of Post's problem of tag and other topics in the theory of Turing machines, Ann. Math. 74, 437-454. MR 25:3825

[1956]

Muchnik, A. A. [1956], On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR N.S. 108, 29-32. MR 18:457a

[2003]

Nies, A. [2003], Parameter definability in the recursively enumerable degrees, to appear in Journal of Mathematical Logic.

[1997]

Nerode, A. and Shore, R. A. [1997], Logic for Applications, Springer, New York,

nd ed. MR 97m:03001

[1998]

Nies, A., Shore, R. A. and Slaman, T. A. [1998], Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77, 241-291. MR 99m:03083

[1930]

Ramsey, F. P. [1930], On a problem of formal logic, Proc. Lond. Math. Soc. (2) 30, 338-384.

[1963]

Sacks, G. E. [1963], Recursive enumerability and the jump operator, Trans. Am. Math. Soc. 108, 223-239. MR 27:5681

[1964]

Sacks, G. E. [1964], The recursively enumerable degrees are dense, Ann. of Math. (2) 80, 300-312. MR 29:3367

[1963]

Shepherdson, J. and Sturgis, H. [1963], Computability of recursive functions, J. Assoc. Comp. Mach 10, 217-255. MR 27:1359

[1978]

Shore, R. A. [1978], On the $\forall\exists$ -sentences of $\alpha$ -recursion theory, in Generalized Recursion Theory II, J. E. Fenstad, R. O. Gandy and G. E. Sacks eds., Studies in Logic and the Foundations of Mathematics 94, North-Holland, Amsterdam, 331-354. MR 80e:03055

[1981]

Shore, R. A. [1981], The theory of the degrees below $0^{\prime}$ , Journal of the London Mathematical Society 24 (1981), 1-14. MR 83m:03051

[1999]

Shore, R. A. [1999], The recursively enumerable degrees, in Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics 140, North-Holland, Amsterdam, 169-197. MR 2000j:03057

[1977]

Simpson, S. G. [1977], First order theory of the degrees of recursive unsolvability, Ann. Math. (2), 105, 121-139. MR 55:5423

[2001]

Slaman, T. A. and Soare, R. I. [2001], Extension of embeddings in the computably enumerable degrees, Annals of Mathematics, 153, 1-43. MR 2002f:03079

[1987]

Soare, R. I. [1987], Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin. MR 88m:03003

[1956]

Spector, C. [1956], On degrees of recursive unsolvability, Ann. Math. (2) 64, 581-592. MR 18:552d

[1966]

Yates, C. E. M. [1966], On the degrees of index sets, Trans. Am. Math. Soc. 121, 309-328. MR 32:2326

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

Russell G. Miller
Affiliation: Department of Mathematics, Queens College (CUNY), 65-30 Kissena Blvd., Flushing, New York 11367
Email: Russell_Miller@qc.edu

Andre O. Nies
Affiliation: Office 592, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
Email: andre@cs.auckland.ac.nz

Richard A. Shore
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: shore@math.cornell.edu

DOI: 10.1090/S0002-9947-03-03406-8
PII: S 0002-9947(03)03406-8
Received by editor(s): October 21, 2002
Posted: October 8, 2003
Additional Notes: The first author was partially supported by a VIGRE Postdoctoral Fellowship under NSF grant number 9983660 to Cornell University. The third author was partially supported by NSF Grant DMS-0100035. The authors offer their thanks to the referee for several helpful comments.
Copyright of article: Copyright 2003, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS