We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has $K \not\leq_{ss} B$ (respectively, $K \not\leq_{\overline{s}} B$): here $\leq_{\overline{s}}$ is the finite-branch version of s-reducibility, $\leq_{ss}$ is the computably bounded version of $\leq_{\overline{s}}$, and $\overline{K}$ is the complement of the halting set. Restriction to $\Sigma^0_2$ sets provides a similar characterization of the $\Sigma^0_2$ hyperhyperimmune sets in terms of s-reducibility. We also showthat no $A \geq_{\overline{s}} \overline{K}$ is hyperhyperimmune. As a consequence, $deg_s (\overline{K})$ is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed.
Chitaia, I.O., Omanadze, R.S.h., Sorbi, A. (2011). Immunity properties and strong positive reducibilities. ARCHIVE FOR MATHEMATICAL LOGIC, 50(3-4), 341-352 [10.1007/s00153-010-0216-5].
Immunity properties and strong positive reducibilities
SORBI, ANDREA
2011-01-01
Abstract
We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has $K \not\leq_{ss} B$ (respectively, $K \not\leq_{\overline{s}} B$): here $\leq_{\overline{s}}$ is the finite-branch version of s-reducibility, $\leq_{ss}$ is the computably bounded version of $\leq_{\overline{s}}$, and $\overline{K}$ is the complement of the halting set. Restriction to $\Sigma^0_2$ sets provides a similar characterization of the $\Sigma^0_2$ hyperhyperimmune sets in terms of s-reducibility. We also showthat no $A \geq_{\overline{s}} \overline{K}$ is hyperhyperimmune. As a consequence, $deg_s (\overline{K})$ is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed.File | Dimensione | Formato | |
---|---|---|---|
oma-chi-sorbi.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
175 kB
Formato
Adobe PDF
|
175 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/22498