Degree spectra of relations on structures of finite computable dimension

Annals of Pure and Applied Logic 115 (1-3):233-277 (2002)
  Copy   BIBTEX


We show that for every computably enumerable degree a > 0 there is an intrinsically c.e. relation on the domain of a computable structure of computable dimension 2 whose degree spectrum is { 0 , a } , thus answering a question of Goncharov and Khoussainov 55–57). We also show that this theorem remains true with α -c.e. in place of c.e. for any α∈ω∪{ω} . A modification of the proof of this result similar to what was done in Hirschfeldt shows that for any α∈ω∪{ω} and any α -c.e. degrees a 0 ,…, a n there is an intrinsically α -c.e. relation on the domain of a computable structure of computable dimension n+1 whose degree spectrum is { a 0 ,…, a n } . These results also hold for m-degree spectra of relations



    Upload a copy of this work     Papers currently archived: 92,873

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Degree spectra of relations on computable structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
Finite computable dimension does not relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Degree spectra of intrinsically C.e. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Effective algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Prime models of finite computable dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.


Added to PP

25 (#651,065)

6 months
12 (#241,878)

Historical graph of downloads
How can I increase my downloads?