On realization of index sets in \(\Pi_1^0\)-classes (Q2300938): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10469-019-09563-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2993713557 / rank | |||
Normal rank |
Revision as of 15:34, 19 March 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