Degree spectra of relations on structures of finite computable dimension

AbstractWe show that for every computably enumerable (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 (Dokl. Math. 55 (1997) 55–57). We also show that this theorem remains true with α-c.e. in place of c.e. for any α∈ω∪{ω}. A modification of the proof of this result similar to what was done in Hirschfeldt (J. Symbolic Logic, to appear) shows that for any α∈ω∪{ω} and any α-c.e. degrees a0,…,an there is an intrinsically α-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