Annals of Pure and Applied Logic 55 (1):51-65 (1991)
AbstractWith 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
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.
Spaces of Orders and Their Turing Degree Spectra.Malgorzata A. Dabkowska, Mieczyslaw K. Dabkowski, Valentina S. Harizanov & Amir A. Togha - 2010 - Annals of Pure and Applied Logic 161 (9):1134-1143.
Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
Degree Spectra of the Successor Relation of Computable Linear Orderings.Jennifer Chubb, Andrey Frolov & Valentina Harizanov - 2009 - Archive for Mathematical Logic 48 (1):7-13.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Review: G. Metakides, A. Nerode, Recursively Enumerable Vector Spaces; G. Metakides, A. Nerode, Effective Content of Field Theory; G. Metakides, A. Nerode, Recursion Theory on Fields and Abstract Dependence. [REVIEW]A. G. Hamilton - 1983 - Journal of Symbolic Logic 48 (3):880-882.
Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.
Computability of Fraïssé Limits.Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (1):66 - 93.
Bounding Homogeneous Models.Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare - 2007 - Journal of Symbolic Logic 72 (1):305 - 323.
Added to PP
Historical graph of downloads
Citations of this work
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
Degrees of Categoricity on a Cone Via Η-Systems.Barbara F. Csima & Matthew Harrison-Trainor - 2017 - Journal of Symbolic Logic 82 (1):325-346.
Π 1 1 Relations and Paths Through.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585-611.
Turing Degrees of Certain Isomorphic Images of Computable Relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
The Possible Turing Degree of the Nonzero Member in a Two Element Degree Spectrum.Valentina S. Harizanov - 1993 - Annals of Pure and Applied Logic 60 (1):1-30.