Some effects of Ash–Nerode and other decidability conditions on degree spectra

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


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



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

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

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

12 (#798,116)

6 months
1 (#419,510)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Valentina Harizanov
George Washington University

References found in this work

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