##
Degree Spectra of Intrinsically C.E. Relations

Status: published in the *Journal of
Symbolic Logic*, vol. 66 (2001), pp. 441 - 469.

Availability: DVI and PostScript

**Abstract.** We show that for every c.e. degree **a** > **0** there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {**0** , **a**}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets *S* there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of *S*. Then we show that if *n* is in \omega or is equal to \omega then for any *n*-c.e. degree **a** > **0** there exists an intrinsically *n*-c.e. relation on the domain of a computable structure whose degree spectrum is {**0** , **a**}. All of these results also hold for m-degree spectra of relations.

drh@math.uchicago.edu