Turing degrees of certain isomorphic images of computable relations (Q1295383): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q247180 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Rodney G. Downey / rank | |||
Normal rank |
Revision as of 20:04, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Turing degrees of certain isomorphic images of computable relations |
scientific article |
Statements
Turing degrees of certain isomorphic images of computable relations (English)
0 references
24 June 1999
0 references
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.
0 references
spectra of computable relations
0 references
computable structure
0 references
Turing degrees
0 references
genericity
0 references