Undecidability and 1-types in intervals of the computably enumerable degrees

DOI10.1016/S0168-0072(99)00011-1MaRDI QIDQ1591201zbMATH OpenOpenAlexWikidataFDO

Authors Denis R. Hirschfeldt, Richard A. Shore, Klaus Ambos-Spies

Publication date 23 October 2001

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0168-0072(99)00011-1

zbMATH Keywords

theories of Turing degreesundecidable theory

Mathematics Subject Classification ID

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

Review text

The authors show that the \(\Pi_5\)-theory of any nontrivial interval \([a,b]\) in the computably enumerable Turing degrees is undecidable in the language \(\left<\leq\right>\) and prove that the elementary theory of this interval has uncountably many 1-types.

Recommendations

• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• An Interval of Computably Enumerable Isolating Degrees
• Undecidability and 1-types in the recursively enumerable degrees
• The Π₃-theory of the -enumeration degrees is undecidable
• Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras

Cites work

• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3305000 (Why is no real title available?)
• Interpretability and Definability in the Recursively Enumerable Degrees
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• On degrees of unsolvability
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• The density of infima in the recursively enumerable degrees
• The density of the nonbranching degrees
• The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical
• The recursively enumerable degrees are dense
• The recursively enumerable degrees have infinitely many one-types
• The undecidability of the recursively enumerable degrees
• Undecidability and 1-types in the recursively enumerable degrees

Cited in

(4)

• The Π₃-theory of the -enumeration degrees is undecidable
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
• Degrees containing members of thin _1⁰ classes are dense and co-dense

This page was built for publication: Undecidability and 1-types in intervals of the computably enumerable degrees

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