Annals of Pure and Applied Logic 93 (1-3):103-113 (1998)

Valentina Harizanov
George Washington University
A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to contain every Turing degree. These conditions imply that if every Turing degree 0″ can be realized in via an isomorphism of the same Turing degree as its image of R, then contains every Turing degree. We also discuss an example of and R whose coincides with the Turing degrees which are 0′
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00056-0
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: 57,156
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

Intrinsically Gs;0alpha; Relations.E. Barker - 1988 - Annals of Pure and Applied Logic 39 (2):105-130.
Intrinsically Alpha º Relations.E. Barker - 1988 - Annals of Pure and Applied Logic 39 (2):105.
Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
Recursive Structures and Ershov's Hierarchy.Christopher J. Ash & Julia F. Knight - 1996 - Mathematical Logic Quarterly 42 (1):461-468.

View all 6 references / Add more references

Citations of this work BETA

Bounding Non- GL ₂ and R.E.A.Klaus Ambos-Spies, Decheng Ding, Wei Wang & Liang Yu - 2009 - Journal of Symbolic Logic 74 (3):989-1000.
Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.

View all 8 citations / Add more citations

Similar books and articles

Turing Degrees of Hypersimple Relations on Computable Structures.Valentina S. Harizanov - 2003 - Annals of Pure and Applied Logic 121 (2-3):209-226.
On Turing Degrees of Points in Computable Topology.Iraj Kalantari & Larry Welch - 2008 - Mathematical Logic Quarterly 54 (5):470-482.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
On Computable Automorphisms of the Rational Numbers.A. S. Morozov & J. K. Truss - 2001 - Journal of Symbolic Logic 66 (3):1458-1470.
Maximal Chains in the Turing Degrees.C. T. Chong & Liang Yu - 2007 - Journal of Symbolic Logic 72 (4):1219 - 1227.


Added to PP index

Total views
36 ( #283,953 of 2,411,819 )

Recent downloads (6 months)
4 ( #188,160 of 2,411,819 )

How can I increase my downloads?


My notes