Annals of Pure and Applied Logic 55 (1):51-65 (1991)

Valentina Harizanov
George Washington University
With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is intrinsically r.e. if and only if a natural recursive-syntactic condition is satisfied. We show that, while a recursive non-intrinsically r.e. relation may have a two element degree spectrum, a non-intrinsically r.e. relation which satisfies the Ash–Nerode decidability condition has an infinite degree spectrum. We also study several related decidability conditions and their effects on the degree spectra, including some conditions which are sufficient to obtain every r.e. degree in a spectrum
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(91)90097-6
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: 55,935
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
Foundations of Recursive Model Theory.Terrence S. Millar - 1978 - Annals of Mathematical Logic 13 (1):45.

Add more references

Citations of this work BETA

Turing Degrees of Certain Isomorphic Images of Computable Relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.

View all 21 citations / Add more citations

Similar books and articles

Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Jack and Jill Have Shifted Spectra.Ned Block - 1999 - Behavioral and Brain Sciences 22 (6):946-947.
Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.
Decidability of an Xstit Logic.Gillman Payette - 2014 - Studia Logica 102 (3):577-607.
The Degree Spectra of Homogeneous Models.Karen Lange - 2008 - Journal of Symbolic Logic 73 (3):1009-1028.


Added to PP index

Total views
11 ( #791,359 of 2,403,176 )

Recent downloads (6 months)
2 ( #361,711 of 2,403,176 )

How can I increase my downloads?


My notes