The -theory of is undecidable

Authors:
Russell G. Miller, Andre O. Nies and Richard A. Shore

Journal:
Trans. Amer. Math. Soc. **356** (2004), 3025-3067

MSC (2000):
Primary 03D25, 03D35; Secondary 03D28

DOI:
https://doi.org/10.1090/S0002-9947-03-03406-8

Published electronically:
October 8, 2003

MathSciNet review:
2052940

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The three quantifier theory of , 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 that lies between the two and three quantifier theories with but includes function symbols.

**Theorem.** *The two quantifier theory of , the r.e. degrees with Turing reducibility, supremum and infimum (taken to be any total function extending the infimum relation on ) is undecidable.*

The same result holds for various lattices of ideals of which are natural extensions of 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 -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 -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 -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 -sentences of -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 ,*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

Retrieve articles in all journals with MSC (2000): 03D25, 03D35, 03D28

Additional Information

**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:
https://doi.org/10.1090/S0002-9947-03-03406-8

Received by editor(s):
October 21, 2002

Published electronically:
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.

Article copyright:
© Copyright 2003
American Mathematical Society