Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms

by Denis R. Hirschfeldt

Status: published in the Journal of Symbolic Logic, vol. 67 (2002), pp. 697 - 720.

Availability: journal version and preprint

Abstract.We give some new examples of possible degree spectra of invariant relations on Δ02-categorical computable structures that demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the kinds of 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 Δ02-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 which kinds 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 Δ02-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.