Immunity properties and strong positive reducibilities (Q535145): 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/s00153-010-0216-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2084571768 / rank | |||
Normal rank |
Revision as of 19:38, 19 March 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