##
Degree Spectra of Relations on Computable Structures in the
Presence of Delta^{0}_{2} Isomorphisms

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

Availability: DVI and PostScript

**Abstract.**We give some new examples of possible degree spectra
of invariant relations on Delta^{0}_{2}-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 Delta^{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 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 Delta^{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.

drh@math.uchicago.edu