Degree spectra of intrinsically C.e. Relations

Journal of Symbolic Logic 66 (2):441-469 (2001)
  Copy   BIBTEX

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 α ∈ ω∪{ω } then for any α-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}. All of these results also hold for m-degree spectra of relations

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,509

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

Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.

Analytics

Added to PP
2009-01-28

Downloads
32 (#362,084)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Intrinsically Gs;0alpha; Relations.E. Barker - 1988 - Annals of Pure and Applied Logic 39 (2):105-130.
Permitting, Forcing, and Copying of a Given Recursive Relation.C. J. Ash, P. Cholak & J. F. Knight - 1997 - Annals of Pure and Applied Logic 86 (3):219-236.

Add more references