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
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 $(\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?)

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

Andre O. Nies
Affiliation: Office 592, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand

Richard A. Shore
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

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