Permitting, forcing, and copying of a given recursive relation

DOI10.1016/S0168-0072(96)00011-5MaRDI QIDQ1365246zbMATH OpenOpenAlexFDO

Authors C. J. Ash, Peter A. Cholak, J. F. Knight

Publication date 14 October 1997

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(96)00011-5

zbMATH Keywords

Ershov's hierarchyforcingpermittingrecursive structure

Mathematics Subject Classification ID

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

Review text

Let \(\mathcal A\) be a recursive structure for a language \(L\) and \(R\) be a relation on \(\mathcal A\). The authors give conditions under which this relation can be made \(\alpha\)-r.e. in Ershov's hierarchy of \(\Delta^0_2\)-sets in an appropriate recursive copy of \(\mathcal A\).

Recommendations

• Possible degrees in recursive copies. II
• Quasi-simple relations in copies of a given recursive structure
• Possible degrees in recursive copies

Cites work

• scientific article; zbMATH DE number 3732033 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Pairs of recursive structures
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Uncountable degree spectra

Cited in

(10)

• Turing degrees of certain isomorphic images of computable relations
• Computable isomorphisms, degree spectra of relations, and Scott families
• Quasi-simple relations in copies of a given recursive structure
• Possible degrees in recursive copies. II
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Degree spectra of relations on structures of finite computable dimension
• Degree spectra of intrinsically c. e. relations
• Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms
• Degree Spectra of Relations on Computable Structures
• Π₁⁰ classes and strong degree spectra of relations

This page was built for publication: Permitting, forcing, and copying of a given recursive relation

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