Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
Journal of Symbolic Logic 61 (3):880-905 (1996)
| Abstract | 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 | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesKlaus Ambos-Spies, André Nies & Richard A. Shore (1992). The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. Journal of Symbolic Logic 57 (3):864-874.
Noam Greenberg (2005). The Role of True Finiteness in the Admissible Recursively Enumerable Degrees. Bulletin of Symbolic Logic 11 (3):398-410.
Peter A. Fejer & Richard A. Shore (1988). Infima of Recursively Enumerable Truth Table Degrees. Notre Dame Journal of Formal Logic 29 (3):420-437.
Paul Fischer (1986). Pairs Without Infimum in the Recursively Enumerable Weak Truth Table Degrees. Journal of Symbolic Logic 51 (1):117-129.
Steven D. Leonhardi (1997). Generalized Nonsplitting in the Recursively Enumerable Degrees. Journal of Symbolic Logic 62 (2):397-437.
Rich Blaylock, Rod Downey & Steffen Lempp (1997). Infima in the Recursively Enumerable Weak Truth Table Degrees. Notre Dame Journal of Formal Logic 38 (3):406-418.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
Frank Stephan (2001). On the Structures Inside Truth-Table Degrees. Journal of Symbolic Logic 66 (2):731-770.
Yuri Gurevich (1983). Decision Problem for Separated Distributive Lattices. Journal of Symbolic Logic 48 (1):193-196.
Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #274,652 of 549,065 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
