Degree spectra of intrinsically CE relations

Authors
Citation
Dr. Hirschfeldt, Degree spectra of intrinsically CE relations, J SYMB LOG, 66(2), 2001, pp. 441-469
Citations number
15
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812 → ACNP
Volume
66
Issue
2
Year of publication
2001
Pages
441 - 469
Database
ISI
SICI code
0022-4812(200106)66:2<441:DSOICR>2.0.ZU;2-V
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 fo r 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 is an el ement of omega boolean OR {omega} then for any alpha -c.e. degree a > 0 the re exists an intrinsically alpha -c.e. relation on the domain of a computab le structure whose degree spectrum is {0.a}. All of these results also hold for m-degree spectra of relations.