On realization of index sets in _1⁰-classes

DOI10.1007/S10469-019-09563-XMaRDI QIDQ2300938zbMATH OpenOpenAlexFDO

Authors Alexander Melnikov, Rodney G. Downey

Publication date 28 February 2020

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10469-019-09563-x

zbMATH Keywords

$\Pi_1^0$-classesindex setrepresentation of index sets

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Review text

A set \(S\) is said to represent an index set \(I\) iff \(I=\{e\mid\exists j\in S(W_e\equiv_TW_j)\}\). The authors prove that for any set \(A<0'\), the set \(\{e\mid W_e\leq_T A\}\) has a \(\Sigma_3^0\)-presentation iff \(A\) is low\(_2\) (in the original text, the condition \(A<0'\) is forgotten). This result gives an answer to a yet unpublished question by B. Csima, R. Downey, and K. M. Ng. I would also like to point out that the cited result of Yates is stated incorrectly: it should be \(\Sigma^0_3\)-completeness for an incomplete c.e. set, not \(\Sigma^0_4\)-completeness for an arbitrary c.e. set. This error, however, does not affect the rest of the proof.

Recommendations

• Index sets for ^0_1 classes
• Index sets in the arithmetical hierarchy
• The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑₅‐Complete
• ON WAYS OF CHARACTERIZING COMPLETE SETS
• The index set {e: W_e ≡₁X}.

Cites work

• scientific article; zbMATH DE number 4172959 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1531920 (Why is no real title available?)
• On the Degrees of Index Sets
• On the Degrees of Index Sets. II

Cited in

(4)

• Index sets of classes of hyper-hypersimple sets
• Index sets for ^0_1 classes
• On the theory of Π¹₃ sets of reals, II
• On the c.e. degrees realizable in ^0_1 classes

This page was built for publication: On realization of index sets in \(\Pi_1^0\)-classes

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