|
|||||
|
|
The  -theory of  is undecidable |
|
| Authors: | Russell G. Miller Andre O. Nies Richard A. Shore |
| Affiliation: | Department of Mathematics, Queens College (CUNY), 65-30 Kissena Blvd., Flushing, New York 11367 ; Office 592, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand ; Department of Mathematics, Cornell University, Ithaca, New York 14853 |
| 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.
The same result holds for various lattices of ideals of |
| Keywords: | |
| 点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息 | |
| 点击此处可从《Transactions of the American Mathematical Society》下载全文 | |
, the r.e. degrees with Turing reducibility, supremum and infimum (taken to be any total function extending the infimum relation on 
) is undecidable. 
which are natural extensions of 
preserving join and infimum when it exits.