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: 93,069

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.
Prime models of computably enumerable degree.Rachel Epstein - 2008 - Journal of Symbolic Logic 73 (4):1373-1388.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.
On Lachlan’s major sub-degree problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.

Analytics

Added to PP
2009-01-28

Downloads
52 (#315,029)

6 months
18 (#152,517)

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