##
Degree Spectra of Relations on Structures of Finite Computable
Dimension

Status: published in the *Annals
of Pure and Applied Logic*, vol. 115 (2002), pp. 233 - 277.

Availability: journal
version and preprint

**Abstract.** We show that for every c.e. degree **a** > **0** there is an intrinsically c.e. relation on the domain
of a computable structure of computable dimension 2 whose degree
spectrum is {**0** , **a**}, thus answering a question of
Goncharov and Khoussainov. We also show that this theorem
remains true with *n-c.e.* in place of *c.e.* for
any *n* less than or equal to omega. A modification of the proof
of this result shows that for any such *n* and any *n*-c.e.
degrees **a**_{0} , . . . , **a**_{n} there is an intrinsically *n*-c.e.
relation on the domain of a computable structure of computable
dimension *n*+1 whose degree spectrum is {**a**_{0} , . . . , **a**_{n}}. These results also hold for m-degree spectra of
relations.

drh@math.uchicago.edu