Degree Spectra of Intrinsically C.E. Relations
Hirschfeldt, Denis R.
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 441-469 / Harvested from Project Euclid
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 $\alpha \in \omega\cup\{\omega \}$ then for any $\alpha$-c.e. degree a > 0 there exists an intrinsically $\alpha$-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.
Publié le : 2001-06-14
Classification: 
@article{1183746453,
     author = {Hirschfeldt, Denis R.},
     title = {Degree Spectra of Intrinsically C.E. Relations},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 441-469},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746453}
}
Hirschfeldt, Denis R. Degree Spectra of Intrinsically C.E. Relations. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  441-469. http://gdmltest.u-ga.fr/item/1183746453/