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

DOI10.2307/2275790zbMath0863.03021OpenAlexW2092944937MaRDI QIDQ5687321

Steffen Lempp, Peter A. Fejer, Ambos-Spies, Klaus, Manuel Lerman

Publication date: 3 June 1997

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275790

zbMATH Keywords

recursively enumerable degreefinite latticesdecision proceduredecidable fragment\(\forall \exists\)-theory of the weak truth-table degreesdistributive upper semi-latticerecursive polynomial many-one degree

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

Continuity of capping in \(\mathcal C_{\text{bT}}\) ⋮ Principal filters definable by parameters in 𝓔_bT ⋮ Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Minimal pairs and complete problems
• Sublattices of the polynomial time degrees
• Cupping and noncapping in the r.e. weak truth table and turing degrees
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• The weak truth table degrees of recursively enumerable sets
• On the Σ₂-theory of the upper semilattice of Turing degrees

This page was built for publication: Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices