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

DOI10.2307/2275790zbMath0863.03021MaRDI QIDQ5687321

Ambos-Spies, Klaus, Peter A. Fejer, Steffen Lempp, 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 degree; finite lattices; decision procedure; decidable fragment; \(\forall \exists\)-theory of the weak truth-table degrees; distributive upper semi-lattice; recursive polynomial many-one degree

Mathematics Subject Classification ID

03B25: Decidability of theories and sets of sentences

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

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

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