The theory of the recursively enumerable weak truth-table degrees is undecidable

DOI10.2307/2275436zbMATH Open0776.03020OpenAlexW2048614185MaRDI QIDQ4032867FDOQ4032867

Authors Klaus Ambos-Spies, André Nies, Richard A. Shore

Publication date 1 April 1993

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

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

zbMATH Keywords

semilatticeelementary theoryr.e. wtt-degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• scientific article; zbMATH DE number 761273
• scientific article; zbMATH DE number 535104
• The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
• scientific article; zbMATH DE number 15488

Cites work

• Classical recursion theory. Vol. II
• Conference in mathematical logic, London 1970
• Recursively enumerable sets and degrees
• Strong reducibilities
• The recursively enumerable degrees have infinitely many one-types
• The weak truth table degrees of recursively enumerable sets

Cited in

(26)

• 1999 European Summer Meeting of the Association for Symbolic Logic
• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• 1998–99 Annual Meeting of the Association for Symbolic Logic
• Weak truth table degrees of structures
• scientific article; zbMATH DE number 15488 (Why is no real title available?)
• scientific article; zbMATH DE number 761273 (Why is no real title available?)
• Boolean pairs formed by the \(\Delta_ n^ 0\)-sets
• The Π₃-theory of the -enumeration degrees is undecidable
• scientific article; zbMATH DE number 3857081 (Why is no real title available?)
• Cupping and noncapping in the r.e. weak truth table and turing degrees
• Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees
• The theory of the \(\alpha \) degrees is undecidable
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• The last question on recursively enumerable \(m\)-degrees
• Classes bounded by incomplete sets
• THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES
• Splitting theorems in recursion theory
• A Useful Undecidable Theory
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
• Every incomplete computably enumerable truth-table degree is branching
• The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
• scientific article; zbMATH DE number 3896923 (Why is no real title available?)
• scientific article; zbMATH DE number 5233159 (Why is no real title available?)
• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• scientific article; zbMATH DE number 1848277 (Why is no real title available?)

This page was built for publication: The theory of the recursively enumerable weak truth-table degrees is undecidable

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