Turing degrees of certain isomorphic images of computable relations
type: Item
instance of: scholarly article
title: Turing degrees of certain isomorphic images of computable relations
zbMATH Open document ID: 0946.03051
DOI: 10.1016/S0168-0072(97)00056-0
author: Valentina Harizanov
published in: Annals of Pure and Applied Logic
publication date: 1999-06-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03D28
Mathematics Subject Classification ID: 03C57
zbMATH DE Number: 1308069
zbMATH Keywords: spectra of computable relations
zbMATH Keywords: computable structure
zbMATH Keywords: Turing degrees
zbMATH Keywords: genericity
reviewed by: Rodney G. Downey
MaRDI profile type: Publication
cites work: Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
cites work: Permitting, forcing, and copying of a given recursive relation
cites work: Quasi-simple relations in copies of a given recursive structure
cites work: Recursive Structures and Ershov's Hierarchy
cites work: Q3919698
cites work: Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
cites work: Q3919704
cites work: Uncountable degree spectra
cites work: Some effects of Ash-Nerode and other decidability conditions on degree spectra
cites work: Q4764109
cites work: Semirecursive Sets and Positive Reducibility
cites work: Q3819052
Recommended article: Turing degrees of hypersimple relations on computable structures
Recommended article: On relative enumerability of Turing degrees
Recommended article: Isomorphism relations on computable structures
Recommended article: Turing computable embeddings of equivalences other than isomorphism
Recommended article: Turing degrees of isomorphism types of algebraic objects
Recommended article: Amenable equivalence relations and Turing degrees
Recommended article: Q3567853
Recommended article: Definable relations in Turing degree structures
Recommended article: Turing degrees in refinements of the arithmetical hierarchy
description: scientific article; zbMATH DE number 1308069