The undecidability of the Π4-theory for the r.e. wtt and Turing degrees

DOI10.2307/2275877MaRDI QIDQ4876314zbMATH OpenOpenAlexFDO

Authors Steffen Lempp, André Nies

Publication date 13 June 1996

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

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

zbMATH Keywords

coding schemefinite bipartite graphspartial orderrecursively enumerable weak truth-table degreesT-degreesundecidability

Mathematics Subject Classification ID

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

Recommendations

• The theory of the recursively enumerable weak truth-table degrees is undecidable
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• scientific article; zbMATH DE number 15488

Cites work

• Anti‐Mitotic Recursively Enumerable Sets
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• Recursively enumerable many-one degrees
• The undecidability of the recursively enumerable degrees
• The weak truth table degrees of recursively enumerable sets
• Undecidability and 1-types in the recursively enumerable degrees

Cited in

(11)

• Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees
• On the strongly bounded Turing degrees of the computably enumerable sets
• scientific article; zbMATH DE number 3880676 (Why is no real title available?)
• The Π₃-theory of the -enumeration degrees is undecidable
• Principal filters definable by parameters in 𝓔_bT
• scientific article; zbMATH DE number 15488 (Why is no real title available?)
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• scientific article; zbMATH DE number 761273 (Why is no real title available?)
• From bi-immunity to absolute undecidability
• Continuity of capping in \(\mathcal C_{\text{bT}}\)

This page was built for publication: The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees

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