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

DOI10.2307/2275877zbMath0846.03018OpenAlexW1982652937MaRDI QIDQ4876314

André Nies, Steffen Lempp

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

undecidabilitypartial ordercoding schemeT-degreesfinite bipartite graphsrecursively enumerable weak truth-table degrees

Mathematics Subject Classification ID

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

Related Items (5)

On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets ⋮ Continuity of capping in \(\mathcal C_{\text{bT}}\) ⋮ Principal filters definable by parameters in 𝓔_bT ⋮ The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable ⋮ Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees

Cites Work

• Unnamed Item
• Undecidability and 1-types in the recursively enumerable degrees
• Recursively enumerable many-one degrees
• The undecidability of the recursively enumerable degrees
• Anti‐Mitotic Recursively Enumerable Sets
• The weak truth table degrees of recursively enumerable sets

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