Immunity properties and strong positive reducibilities (Q535145): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:54, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Immunity properties and strong positive reducibilities |
scientific article |
Statements
Immunity properties and strong positive reducibilities (English)
0 references
11 May 2011
0 references
The paper's results turn on reducibilities derived from \(Q\)-reducibility. Recall that \(A\leq_QB\) iff, for some computable function \(f\) (the reduction function), \(x\in A\Leftrightarrow W_{f(x)}\subseteq B\) for every \(x\). For \(B\neq\emptyset\), say \(A\leq_sB\) iff \(\overline A\leq_Q\overline B\), and \(A\leq_{\overline s}B\) if this holds via a reduction function \(f\) that makes \(W_{f(x)}\) finite for every \(x\). A main result is that a set \(A\) is hyperhyperimmune iff there is no infinite subset \(B\) of \(A\) for which \(\overline K\leq_{\overline s}B\), where \(K\) is the halting set. It follows that no set \(\geq_{\overline s}K\) is hyperhyperimmune. Parallel characterizations are derived for hyperimmunity and for hyperhyperimmunity among \(\Sigma^0_2\) sets. A corollary answering an open question is that the hyperhyperimmune \(s\)-degrees are not upward closed.
0 references
\(Q\)-reducibility
0 references
\(s\)-reducibility
0 references
hyperimmune set
0 references
hyperhyperimmune set
0 references