Avoiding uniformity in the \(\Delta_2^0\) enumeration degrees

DOI10.1016/j.apal.2014.04.008zbMath1351.03030OpenAlexW2047884664MaRDI QIDQ2453064

Liliana Badillo, Charles M. Harris

Publication date: 6 June 2014

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

Full work available at URL: https://doi.org/10.1016/j.apal.2014.04.008

zbMATH Keywords

degreelowErshov hierarchyenumeration reducibilitycappablearithmetical uniformityhighincomparable degree

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Related Items

Automorphisms ofη-like computable linear orderings and Kierstead's conjecture ⋮ INITIAL SEGMENTS OF THE ENUMERATION DEGREES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Goodness in the enumeration and singleton degrees
• The \(n\)-rea enumeration degrees are dense
• Classical recursion theory. Vol. II
• Limit lemmas and jump inversion in the enumeration degrees
• Computable structures and the hyperarithmetical hierarchy
• The limitations of cupping in the local structure of the enumeration degrees
• On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
• Properly Σ2 Enumeration Degrees
• Reducibility and Completeness for Sets of Integers
• On minimal pairs of enumeration degrees
• Semirecursive Sets and Positive Reducibility
• Degrees in Which the Recursive Sets are Uniformly Recursive