1996], Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices

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 nite lattices which can be embedded into the re wttdegrees by a map which preserves the least and greatest elements A nite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the lter generated by its cuppable elements are disjoint We formulate general criteria that allow one to conclude that a distributive upper semilattice has a decidable twoquantier theory These criteria are applied not only to the weak truthtable degrees of the recursively enumerable sets but also to various substructures of the polynomial manyone pm degrees of the recursive sets These applications to the pm degrees require no new complexitytheoretic results The fact that the pmdegrees of the recursive sets have a decidable twoquantier theory answers a question raised by Shore and Slaman i