Immunity properties and strong positive reducibilities (Q535145): Difference between revisions

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.