Relative to any non-hyperarithmetic set
From MaRDI portal
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.
The degree spectrum of a countable structure \(M\) is defined as the collection of all Turing degrees which compute an isomorphic copy of \(M\) whose universe is the subset of the set of natural numbers.NEWLINENEWLINEThe main results of the paper are the following statements: 1) there is a countable linear ordering whose degree spectrum consists of the non-hyperarithmetic degrees; 2) there is a structure whose degree spectrum is null and co-meager; 3) there is a structure whose degree spectrum is meager and co-null.
Recommendations
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)- Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
- Degree spectra of structures relative to equivalences
- Degree spectra of structures
- Limitwise monotonic spectra and their generalizations
- Effective categoricity for distributive lattices and Heyting algebras
- Natural large degree spectra
- Spectra of high_n and non-low_n degrees
- Enumeration reducibility and computable structure theory
- Degree spectra of equivalence relations
- The Slaman-Wehner theorem in higher recursion theory
- ω-Degree Spectra
- Uniformity results on the Baire property
- Theory spectra and classes of theories
- Continuous higher randomness
- On decidable and computable models of theories
- Spectra of theories and structures
- scientific article; zbMATH DE number 7332477 (Why is no real title available?)
- A local version of the Slaman-Wehner theorem and families closed under finite differences
- On complete and almost complete constructive metric spaces
- An effective analysis of the Denjoy rank
- New degree spectra of Polish spaces
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)
