Degree spectra of intrinsically C.e. Relations

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

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,545
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.

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
14 ( #515,236 of 2,325,366 )

Recent downloads (6 months)
4 ( #409,683 of 2,325,366 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature