Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The $\forall\exists$-theory of $\mathcal{R}(\leq,\vee,\wedge)$ 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 $(\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 [Enhancements On Off] (What's this?)

  • [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, $2$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

Similar Articles

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

American Mathematical Society