Turing degrees of certain isomorphic images of computable relations
The author continues her investigations of the possible spectra of a relation \(R\) on a computable structure \(A\). Here the spectrum is defined as the possible degrees of images of \(R\) in computable copies of \(A\). She gives conditions for \(\text{spec}(R)\) to be the Turing degrees. These conditions give as a corollary the result independently obtained by \textit{C. J. Ash}, \textit{P. Cholak}, and \textit{J. F. Knight} [``Permitting, forcing, and copying of a given recursive relation, Ann. Pure Appl. Log. 86, No. 3, 219-236 (1997; Zbl 0883.03029)] that if \(R\) has copies for all \(\Delta_3\) degrees, via isomorphisms of the same degrees, then the spectrum is all of the degrees. The proof also uses genericity. The author also gives an example, based on work of Jockusch, that there is a relation \(R\) whose spectrum is all the \(\Delta_2\) degrees.
- Turing degrees of hypersimple relations on computable structures
- On relative enumerability of Turing degrees
- Isomorphism relations on computable structures
- Turing computable embeddings of equivalences other than isomorphism
- Turing degrees of isomorphism types of algebraic objects
- Amenable equivalence relations and Turing degrees
- Turing degrees and the Ershov hierarchy
- Definable relations in Turing degree structures
- Definable relations in Turing degree structures
- Turing degrees in refinements of the arithmetical hierarchy
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- scientific article; zbMATH DE number 3732033 (Why is no real title available?)
- scientific article; zbMATH DE number 3732038 (Why is no real title available?)
- scientific article; zbMATH DE number 749928 (Why is no real title available?)
- Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
- Permitting, forcing, and copying of a given recursive relation
- Quasi-simple relations in copies of a given recursive structure
- Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
- Recursive Structures and Ershov's Hierarchy
- Semirecursive Sets and Positive Reducibility
- Some effects of Ash-Nerode and other decidability conditions on degree spectra
- Uncountable degree spectra
- The possible Turing degree of the nonzero member in a two element degree spectrum
- Turing degrees of hypersimple relations on computable structures
- Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
- Degree spectra of relations on structures of finite computable dimension
- On dark computably enumerable equivalence relations
- Possible degrees in recursive copies
- The definability strength of combinatorial principles
- Degree spectra of relations on computable structures in the presence of Δ20isomorphisms
- Bounding non-GL2 and R.E.A.
- Degree Spectra of Relations on Computable Structures
- Turing degrees of isomorphism types of algebraic objects
- Domination, forcing, array nonrecursiveness and relative recursive enumerability
- Π10 classes and strong degree spectra of relations
- Computable reducibility for computable linear orders of type
- A note on joins and meets for positive linear preorders
- On learning families of ideals in lattices and Boolean algebras
- On learning down-sets in quasi-orders, and ideals in Boolean algebras
- On the theory of computably enumerable linear preorders with concatenation
This page was built for publication: Turing degrees of certain isomorphic images of computable relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295383)
