On realization of index sets in \(\Pi_1^0\)-classes (Q2300938): Difference between revisions

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.