Degree Spectra of Relations on Computable Structures in the
Presence of Δ02 Isomorphisms
Status: published in the Journal
of
Symbolic Logic 67 (2002) 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.
drh@math.uchicago.edu