Degree Spectra of Intrinsically C.E. Relations
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