Degree Spectra of Intrinsically C.E. Relations

by Denis R. Hirschfeldt



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

Availability: journal version and preprint

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