Degree Spectra of Relations on Structures of Finite Computable Dimension

by Denis R. Hirschfeldt



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

Availability: DVI and PostScript

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