Turing degrees of certain isomorphic images of computable relations

DOI10.1016/S0168-0072(97)00056-0zbMath0946.03051MaRDI QIDQ1295383

Valentina S. Harizanov

Publication date: 24 June 1999

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

genericitycomputable structureTuring degreesspectra of computable relations

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Other Turing degree structures (03D28)

Related Items

Degree spectra of relations on structures of finite computable dimension ⋮ On dark computably enumerable equivalence relations ⋮ Computable reducibility for computable linear orders of type \(\omega \) ⋮ THE DEFINABILITY STRENGTH OF COMBINATORIAL PRINCIPLES ⋮ Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures ⋮ Domination, forcing, array nonrecursiveness and relative recursive enumerability ⋮ Π₁⁰ classes and strong degree spectra of relations ⋮ Bounding non-GL₂ and R.E.A. ⋮ Degree Spectra of Relations on Computable Structures ⋮ Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Uncountable degree spectra
• Quasi-simple relations in copies of a given recursive structure
• Permitting, forcing, and copying of a given recursive relation
• Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
• Semirecursive Sets and Positive Reducibility
• Recursive Structures and Ershov's Hierarchy