Π10 classes and strong degree spectra of relations

DOI10.2178/jsl/1191333852zbMath1123.03025OpenAlexW2149637938MaRDI QIDQ5422314

Sarah Pingrey, Timothy H. McNicholl, Denis R. Hirschfeldt, Carl G. jun. Jockusch, Jennifer Chubb, Valentina S. Harizanov, J. S. Roy Chisholm

Publication date: 17 October 2007

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

Full work available at URL: https://projecteuclid.org/euclid.jsl/1191333852

zbMATH Keywords

Kolmogorov complexitycomputable structurestruth-table degreesweak truth-table degreesscattered computable linear ordering

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computable structure theory, computable model theory (03C57) Other Turing degree structures (03D28)

Related Items (4)

A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Weak truth table degrees of structures

Cites Work

• Unnamed Item
• Unnamed Item
• Members of countable \(\Pi ^ 0_ 1\) classes
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Uncountable degree spectra
• On \(\Pi{}^ 0_ 1\) classes and their ranked points
• Turing degrees of certain isomorphic images of computable relations
• Dynamic notions of genericity and array noncomputability
• Permitting, forcing, and copying of a given recursive relation
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Computable structures and the hyperarithmetical hierarchy
• Countable retracing functions and \(\Pi_2^0\) predicates
• Hypersimplicity and semicomputability in the weak truth table degrees
• Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms
• Degree Spectra of Relations on Computable Structures
• Intrinsic Reducibilities
• Class groups of integral group rings

This page was built for publication: Π₁⁰ classes and strong degree spectra of relations