Turing degrees of hypersimple relations on computable structures

DOI10.1016/S0168-0072(02)00113-6MaRDI QIDQ1399102zbMATH OpenOpenAlexFDO

Authors Valentina Harizanov

Publication date 30 July 2003

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

Full work available at URL https://doi.org/10.1016/s0168-0072(02)00113-6

zbMATH Keywords

computable structurehypersimple relationTuring degree

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45)

Review text

The author studies spectral type questions for distinguished \(R\) relations on computable structures \(A\). Assuming the relation in question is formally hypersimple, a syntactic condition introduced by \textit{G. R. Hird} [in his thesis and in Ann. Pure Appl. Logic 63, 241-269 (1993; Zbl 0793.03036)]. The author gives general syntactic conditions for the existence of a computable copy of \(A\) containing a hypersimple copy of \(R\) in each non-zero Turing degree. Applications include some results of Remmel on Boolean algebras.

Recommendations

• Turing degrees of certain isomorphic images of computable relations
• scientific article; zbMATH DE number 1421072
• Degree Spectra of Relations on Computable Structures
• Simple and immune relations on countable structures
• Relatively Hyperimmune Relations on Structures

Cites work

• A Theorem on Hypersimple Sets
• scientific article; zbMATH DE number 3914305 (Why is no real title available?)
• scientific article; zbMATH DE number 3732033 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1303202 (Why is no real title available?)
• scientific article; zbMATH DE number 749928 (Why is no real title available?)
• scientific article; zbMATH DE number 1421072 (Why is no real title available?)
• Quasi-simple relations in copies of a given recursive structure
• Recursive isomorphism types of recursive Boolean algebras
• Recursive properties of relations on models
• Recursively enumerable sets of positive integers and their decision problems
• Recursively enumerable vector spaces
• Semirecursive Sets and Positive Reducibility
• Simple and immune relations on countable structures
• Some effects of Ash-Nerode and other decidability conditions on degree spectra

Cited in

(10)

• Turing degrees of certain isomorphic images of computable relations
• Simple and immune relations on countable structures
• Degree spectra of relations on structures of finite computable dimension
• On the degree structure of equivalence relations under computable reducibility
• Hypersimplicity and semicomputability in the weak truth table degrees
• scientific article; zbMATH DE number 5504384 (Why is no real title available?)
• Degree Spectra of Relations on Computable Structures
• scientific article; zbMATH DE number 1390015 (Why is no real title available?)
• scientific article; zbMATH DE number 1421072 (Why is no real title available?)
• Relatively Hyperimmune Relations on Structures

This page was built for publication: Turing degrees of hypersimple relations on computable structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399102)