Degree spectra of relations on structures of finite computable dimension

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

Abstract

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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,667

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

Degree spectra of intrinsically C.e. Relations.Denis Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Degree spectra of relations on a cone.Matthew Harrison-Trainor - 2018 - Providence, RI: American Mathematical Society.

Analytics

Added to PP
2014-01-16

Downloads
37 (#615,120)

6 months
11 (#359,362)

Historical graph of downloads
How can I increase my downloads?