David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 67 (2):697 - 720 (2002)
We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 -categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses  to establish the same result for computable relations on computable linear orderings. We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ 0 2 -categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode  to extend results of Harizanov 
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Denis R. Hirschfeldt (2002). Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms. Journal of Symbolic Logic 67 (2):697 - 720.
Denis R. Hirschfeldt (2001). Degree Spectra of Intrinsically C.E. Relations. Journal of Symbolic Logic 66 (2):441-469.
Denis R. Hirschfeldt (2000). Degree Spectra of Relations on Computable Structures. Bulletin of Symbolic Logic 6 (2):197-212.
Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore (2013). Degrees of Categoricity and the Hyperarithmetic Hierarchy. Notre Dame Journal of Formal Logic 54 (2):215-231.
Walker M. White & Denis R. Hirschfeldt (2002). Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures. Notre Dame Journal of Formal Logic 43 (1):51-64.
Russell Miller (2001). The Δ02-Spectrum of a Linear Order. Journal of Symbolic Logic 66 (2):470 - 486.
Michael Moses (2010). The Block Relation in Computable Linear Orders. Notre Dame Journal of Formal Logic 52 (3):289-305.
Wesley Calvert (2005). The Isomorphism Problem for Computable Abelian P-Groups of Bounded Length. Journal of Symbolic Logic 70 (1):331 - 345.
Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon (2005). Computable Categoricity of Trees of Finite Height. Journal of Symbolic Logic 70 (1):151-215.
Joseph S. Miller (2004). Degrees of Unsolvability of Continuous Functions. Journal of Symbolic Logic 69 (2):555 - 584.
Barbara F. Csima (2004). Degree Spectra of Prime Models. Journal of Symbolic Logic 69 (2):430 - 442.
Russell Miller (2005). The Computable Dimension of Trees of Infinite Height. Journal of Symbolic Logic 70 (1):111-141.
E. Herrman (2001). Infinite Chains and Antichains in Computable Partial Orderings. Journal of Symbolic Logic 66 (2):923-934.
Denis R. Hirschfeldt, Bakhadyr Khoussainov & Richard A. Shore (2003). A Computably Categorical Structure Whose Expansion by a Constant has Infinite Computable Dimension. Journal of Symbolic Logic 68 (4):1199-1241.
Added to index2010-08-24
Total downloads2 ( #677,558 of 1,792,164 )
Recent downloads (6 months)1 ( #464,595 of 1,792,164 )
How can I increase my downloads?