Relative to any non-hyperarithmetic set

DOI10.1142/S0219061312500079MaRDI QIDQ2853977zbMATH OpenFDO

Authors Noam Greenberg, Antonio Montalbán, Theodore A. Slaman

Publication date 17 October 2013

Published in Journal of Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1907

zbMATH Keywords

computable structurehyperarithmeticdegree spectrum

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Other Turing degree structures (03D28) Theory of numerations, effectively presented structures (03D45)

Abstract: We prove that there is a structure, indeed a linear ordering, whose degree spectrum is the set of all non-hyperarithmetic degrees. We also show that degree spectra can distinguish measure from category.

Recommendations

• Relativized Degree Spectra
• Spectra of high\(_n\) and non-low\(_n\) degrees
• The _2⁰-spectrum of a linear order
• Logical Approaches to Computational Barriers
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures

Cites work

• Computable structures and the hyperarithmetical hierarchy
• Computable trees, prime models, and relative decidability
• Degree spectra and immunity properties
• Enumerations in computable structure theory
• Enumerations, countable structures and Turing degrees
• Pairs of recursive structures
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Recursive in a generic real
• Recursively presentable prime models
• Relative to any nonrecursive set
• Spectra of degrees of some structures
• Spectra of high\(_n\) and non-low\(_n\) degrees
• The Slaman-Wehner theorem in higher recursion theory

Cited in

(21)

• New degree spectra of Polish spaces
• Degree spectra of equivalence relations
• Spectra of high\(_n\) and non-low\(_n\) degrees
• Limitwise monotonic spectra and their generalizations
• Uniformity results on the Baire property
• A local version of the Slaman-Wehner theorem and families closed under finite differences
• Degree spectra of structures relative to equivalences
• Effective categoricity for distributive lattices and Heyting algebras
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Theory spectra and classes of theories
• On decidable and computable models of theories
• Enumeration reducibility and computable structure theory
• scientific article; zbMATH DE number 7332477 (Why is no real title available?)
• Spectra of theories and structures
• On complete and almost complete constructive metric spaces
• ω-Degree Spectra
• Natural large degree spectra
• An effective analysis of the Denjoy rank
• The Slaman-Wehner theorem in higher recursion theory
• Degree spectra of structures
• Continuous higher randomness

This page was built for publication: Relative to any non-hyperarithmetic set

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