Degree Spectra of Relations on Structures of Finite Computable
Dimension
Status: published in the Annals
of Pure and Applied Logic 115 (2002) 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 a0 , . . . , an there is an intrinsically n-c.e.
relation on the domain of a computable structure of computable
dimension n+1 whose degree spectrum is {a0 , . . . , an}. These results also hold for m-degree spectra of
relations.
drh@math.uchicago.edu