The theory of D(,,') is undecidable

MaRDI QIDQ5477365zbMATH OpenFDO

Authors Richard A. Shore, Theodore A. Slaman

Publication date 3 July 2006

zbMATH Keywords

Turing degreesundecidability

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• The \(n\)-r.e. degrees: undecidability and \(\Sigma_1\) substructures
• On the Σ₂-theory of the upper semilattice of Turing degrees
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
• Decidability and Invariant Classes for Degree Structures

Cited in

(8)

• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• scientific article; zbMATH DE number 39360 (Why is no real title available?)
• The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
• scientific article; zbMATH DE number 6829362 (Why is no real title available?)
• Embedding jump upper semilattices into the Turing degrees
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable
• On the Σ₂-theory of the upper semilattice of Turing degrees

This page was built for publication: The \(\forall\exists\) theory of \({\mathcal D}(\leq,\vee,{}')\) is undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5477365)