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.
2011
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/22498