##
Degree Spectra of Intrinsically C.E. Relations

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

Availability: journal
version and preprint

**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
ω or is equal to ω 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