Π10 classes and strong degree spectra of relations

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

Timothy H. McNicholl, Denis R. Hirschfeldt, Valentina S. Harizanov, Jennifer Chubb, Carl G. jun. Jockusch, Sarah Pingrey, 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 complexity; computable structures; truth-table degrees; weak truth-table degrees; scattered computable linear ordering

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03C57: Computable structure theory, computable model theory

03D28: Other Turing degree structures

Related Items

Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees

Cites Work

• Unnamed Item
• 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
• Class groups of integral group rings