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

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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2695024
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,319
Through your library

References found in this work BETA

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

Citations of this work BETA

Degrees of Orders on Torsion-Free Abelian Groups.Asher M. Kach, Karen Lange & Reed Solomon - 2013 - Annals of Pure and Applied Logic 164 (7-8):822-836.

View all 6 citations / Add more citations

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 index
2009-01-28

Total views
32 ( #339,486 of 2,448,741 )

Recent downloads (6 months)
1 ( #447,034 of 2,448,741 )

How can I increase my downloads?

Downloads

My notes