Journal of Symbolic Logic 61 (3):880-905 (1996)

We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]
Keywords Recursively enumerable weak truth-table degree   recursive polynomial manyone degree   decidable fragment
Categories (categorize this paper)
DOI 10.2307/2275790
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,756
Through your library

References found in this work BETA

Lattice Theory.Garrett Birkhoff - 1940 - Journal of Symbolic Logic 5 (4):155-157.

Add more references

Citations of this work BETA

Interpreting N in the Computably Enumerable Weak Truth Table Degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
Continuity of Capping in C bT.Paul Brodhead, Angsheng Li & Weilin Li - 2008 - Annals of Pure and Applied Logic 155 (1):1-15.

Add more citations

Similar books and articles

Decision Problem for Separated Distributive Lattices.Yuri Gurevich - 1983 - Journal of Symbolic Logic 48 (1):193-196.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
On the Orbits of Hyperhypersimple Sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
Infima of Recursively Enumerable Truth Table Degrees.Peter A. Fejer & Richard A. Shore - 1988 - Notre Dame Journal of Formal Logic 29 (3):420-437.
Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.


Added to PP index

Total views
52 ( #179,470 of 2,333,957 )

Recent downloads (6 months)
4 ( #194,495 of 2,333,957 )

How can I increase my downloads?


My notes