The ∀∃-theory of ℛ(≤,∨,∧) is undecidable

Miller, Russell; Nies, Andre; Shore, Richard

doi:10.1090/S0002-9947-03-03406-8

The $\forall \exists$-theory of $\mathcal {R}(\leq ,\vee ,\wedge )$ is undecidable
HTML articles powered by AMS MathViewer

by Russell G. Miller, Andre O. Nies and Richard A. Shore PDF

Trans. Amer. Math. Soc. 356 (2004), 3025-3067 Request permission

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.

References

Bernays, P. and Schoenfikel, M. [1928], Zum Entscheidungsproblem der mathematischen Logik, Math. Ann. 99, 342-372.
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, DOI 10.1007/978-3-642-59207-2
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, DOI 10.1016/0168-0072(93)90207-T
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, DOI 10.2307/2694975
Burton Dreben and Warren D. Goldfarb, The decision problem, Advanced Book Program, Addison-Wesley Publishing Co., Reading, Mass., 1979. Solvable classes of quantificational formulas. MR 548005
Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620, DOI 10.1007/BFb0067135
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
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, DOI 10.1090/S0273-0979-1982-14970-9
Carl G. Jockusch Jr. and Theodore A. Slaman, On the $\Sigma _2$-theory of the upper semilattice of Turing degrees, J. Symbolic Logic 58 (1993), no. 1, 193–204. MR 1217184, DOI 10.2307/2275332
Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
A. H. Lachlan, The impossibility of finding relative complements for recursively enumerable degrees, J. Symbolic Logic 31 (1966), 434–454. MR 205847, DOI 10.2307/2270459
A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472. MR 237331, DOI 10.1002/malq.19680143002
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 409150, DOI 10.1016/0003-4843(76)90016-4
Steffen Lempp, André Nies, and Theodore A. Slaman, The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable, Trans. Amer. Math. Soc. 350 (1998), no. 7, 2719–2736. MR 1389784, DOI 10.1090/S0002-9947-98-01800-5
Manuel Lerman, Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93 (1971), 365–389. MR 307893, DOI 10.2307/1970779
Manuel Lerman, Admissible ordinals and priority arguments, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Lecture Notes in Math., Vol. 337, Springer, Berlin, 1973, pp. 311–344. MR 0379153
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
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, DOI 10.1016/S0168-0072(99)00021-4
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, DOI 10.1090/S0002-9947-1988-0973174-0
M. Lerman, R. A. Shore, and R. I. Soare, The elementary theory of the recursively enumerable degrees is not $\aleph _{0}$-categorical, Adv. in Math. 53 (1984), no. 3, 301–320. MR 753871, DOI 10.1016/0001-8708(84)90028-8
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 140405, DOI 10.2307/1970290
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
Nies, A. [2003], Parameter definability in the recursively enumerable degrees, to appear in Journal of Mathematical Logic.
Anil Nerode and Richard A. Shore, Logic for applications, 2nd ed., Graduate Texts in Computer Science, Springer-Verlag, New York, 1997. MR 1442711, DOI 10.1007/978-1-4612-0649-1
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, DOI 10.1112/S002461159800046X
Ramsey, F. P. [1930], On a problem of formal logic, Proc. Lond. Math. Soc. (2) 30, 338-384.
Gerald E. Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223–239. MR 155747, DOI 10.1090/S0002-9947-1963-0155747-3
Gerald E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312. MR 166089, DOI 10.2307/1970393
J. C. Shepherdson and H. E. Sturgis, Computability of recursive functions, J. Assoc. Comput. Mach. 10 (1963), 217–255. MR 151374, DOI 10.1145/321160.321170
Richard A. Shore, On the $\forall \exists$-sentences of $\alpha$-recursion theory, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Studies in Logic and the Foundations of Mathematics, vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 331–353. MR 516943
Richard A. Shore, The theory of the degrees below ${\bf 0}^{\prime }$, J. London Math. Soc. (2) 24 (1981), no. 1, 1–14. MR 623666, DOI 10.1112/jlms/s2-24.1.1
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, DOI 10.1016/S0049-237X(99)80022-6
Stephen G. Simpson, First-order theory of the degrees of recursive unsolvability, Ann. of Math. (2) 105 (1977), no. 1, 121–139. MR 432435, DOI 10.2307/1971028
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, DOI 10.2307/3062109
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, DOI 10.1007/978-3-662-02460-7
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309–328. MR 184855, DOI 10.1090/S0002-9947-1966-0184855-9