On realization of index sets in \(\Pi_1^0\)-classes (Q2300938): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:19, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On realization of index sets in \(\Pi_1^0\)-classes |
scientific article |
Statements
On realization of index sets in \(\Pi_1^0\)-classes (English)
0 references
28 February 2020
0 references
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.
0 references
index set
0 references
$\Pi_1^0$-classes
0 references
representation of index sets
0 references