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 Free Access

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]**Egon Börger, Erich Grädel, and Yuri Gurevich,*The classical decision problem*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1997. With an appendix by Cyril Allauzen and Bruno Durand. MR**1482227****[1993]**William C. Calhoun,*Incomparable prime ideals of recursively enumerable degrees*, Ann. Pure Appl. Logic**63**(1993), no. 1, 39–56. 9th International Congress of Logic, Methodology and Philosophy of Science (Uppsala, 1991). MR**1238107**, https://doi.org/10.1016/0168-0072(93)90207-T**[2001]**William C. Calhoun and Manuel Lerman,*Embedding finite lattices into the ideals of computably enumerable Turing degrees*, J. Symbolic Logic**66**(2001), no. 4, 1791–1802. MR**1877022**, https://doi.org/10.2307/2694975**[1979]**Burton Dreben and Warren D. Goldfarb,*The decision problem*, Addison-Wesley Publishing Co., Reading, Mass., 1979. Solvable classes of quantificational formulas; Advanced Book Program. MR**548005****[1979]**Richard L. Epstein,*Degrees of unsolvability: structure and theory*, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR**551620****[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]**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**, https://doi.org/10.1090/S0273-0979-1982-14970-9**[1993]**Carl G. Jockusch Jr. and Theodore A. Slaman,*On the Σ₂-theory of the upper semilattice of Turing degrees*, J. Symbolic Logic**58**(1993), no. 1, 193–204. MR**1217184**, https://doi.org/10.2307/2275332**[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]**A. H. Lachlan,*The impossibility of finding relative complements for recursively enumerable degrees*, J. Symbolic Logic**31**(1966), 434–454. MR**0205847**, https://doi.org/10.2307/2270459**[1968]**A. H. Lachlan,*Distributive initial segments of the degrees of unsolvability*, Z. Math. Logik Grundlagen Math.**14**(1968), 457–472. MR**0237331****[1975]**Alistair H. Lachlan,*A recursively enumerable degree which will not split over all lesser ones*, Ann. Math. Logic**9**(1976), no. 4, 307–365. MR**0409150**, https://doi.org/10.1016/0003-4843(76)90016-4**[1998]**Steffen Lempp, André Nies, and Theodore A. Slaman,*The Π₃-theory of the computably enumerable Turing degrees is undecidable*, Trans. Amer. Math. Soc.**350**(1998), no. 7, 2719–2736. MR**1389784**, https://doi.org/10.1090/S0002-9947-98-01800-5**[1971]**Manuel Lerman,*Initial segments of the degrees of unsolvability*, Ann. of Math. (2)**93**(1971), 365–389. MR**0307893**, https://doi.org/10.2307/1970779**[1973]**Manuel Lerman,*Admissible ordinals and priority arguments*, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Springer, Berlin, 1973, pp. 311–344. Lecture Notes in Math., Vol. 337. MR**0379153****[1983]**Manuel Lerman,*Degrees of unsolvability*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR**708718****[2000]**M. Lerman,*A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees*, Ann. Pure Appl. Logic**101**(2000), no. 2-3, 275–297. MR**1736064**, https://doi.org/10.1016/S0168-0072(99)00021-4**[1988]**Manuel Lerman and Richard A. Shore,*Decidability and invariant classes for degree structures*, Trans. Amer. Math. Soc.**310**(1988), no. 2, 669–692. MR**973174**, https://doi.org/10.1090/S0002-9947-1988-0973174-0**[1984]**M. Lerman, R. A. Shore, and R. I. Soare,*The elementary theory of the recursively enumerable degrees is not ℵ₀-categorical*, Adv. in Math.**53**(1984), no. 3, 301–320. MR**753871**, https://doi.org/10.1016/0001-8708(84)90028-8**[1961]**Marvin L. Minsky,*Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines*, Ann. of Math. (2)**74**(1961), 437–455. MR**0140405**, https://doi.org/10.2307/1970290**[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]**Anil Nerode and Richard A. Shore,*Logic for applications*, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR**1442711****[1998]**André Nies, Richard A. Shore, and Theodore A. Slaman,*Interpretability and definability in the recursively enumerable degrees*, Proc. London Math. Soc. (3)**77**(1998), no. 2, 241–291. MR**1635141**, https://doi.org/10.1112/S002461159800046X**[1930]**Ramsey, F. P. [1930], On a problem of formal logic,*Proc. Lond. Math. Soc.*(2)**30**, 338-384.**[1963]**Gerald E. Sacks,*Recursive enumerability and the jump operator*, Trans. Amer. Math. Soc.**108**(1963), 223–239. MR**0155747**, https://doi.org/10.1090/S0002-9947-1963-0155747-3**[1964]**Gerald E. Sacks,*The recursively enumerable degrees are dense*, Ann. of Math. (2)**80**(1964), 300–312. MR**0166089**, https://doi.org/10.2307/1970393**[1963]**J. C. Shepherdson and H. E. Sturgis,*Computability of recursive functions*, J. Assoc. Comput. Mach.**10**(1963), 217–255. MR**0151374**, https://doi.org/10.1145/321160.321170**[1978]**Richard A. Shore,*On the ∀∃-sentences of 𝛼-recursion theory*, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Stud. Logic Foundations Math., vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 331–353. MR**516943****[1981]**Richard A. Shore,*The theory of the degrees below 0′*, J. London Math. Soc. (2)**24**(1981), no. 1, 1–14. MR**623666**, https://doi.org/10.1112/jlms/s2-24.1.1**[1999]**Richard A. Shore,*The recursively enumerable degrees*, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 169–197. MR**1720763**, https://doi.org/10.1016/S0049-237X(99)80022-6**[1977]**Stephen G. Simpson,*First-order theory of the degrees of recursive unsolvability*, Ann. of Math. (2)**105**(1977), no. 1, 121–139. MR**0432435**, https://doi.org/10.2307/1971028**[2001]**Theodore A. Slaman and Robert I. Soare,*Extension of embeddings in the computably enumerable degrees*, Ann. of Math. (2)**154**(2001), no. 1, 1–43. MR**1847587**, https://doi.org/10.2307/3062109**[1987]**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****[1956]**Spector, C. [1956], On degrees of recursive unsolvability,*Ann. Math. (2)***64**, 581-592. MR**18:552d****[1966]**C. E. M. Yates,*On the degrees of index sets*, Trans. Amer. Math. Soc.**121**(1966), 309–328. MR**0184855**, https://doi.org/10.1090/S0002-9947-1966-0184855-9

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