Degree Spectra of Intrinsically C.E. Relations

by Denis R. Hirschfeldt



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

Availability: DVI and PostScript

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 \omega or is equal to \omega 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