We investigate immunity properties of the s-degrees. In particular we show that neither the immune nor the hyperimmune s-degrees are upwards closed since there exist $\Delta^0_2$ s-degrees $a \leq_s b$ such that $a$ is hyperimmune, but $b$ is immune free. We also show that there is no hyperhyperimmune $\Pi^0_2$ set A such that $\overline{K} \leq_{\overline{s}} A$, where $\overline{K}$ is the complement of the halting set and $ \leq_{\overline{s}}$ denotes the finite-branch version of s-reducibility.
Omanadze, R.S.h., Sorbi, A. (2010). Immunity properties of the s-degrees. GEORGIAN MATHEMATICAL JOURNAL, 17(3), 563-579 [10.1515/GMJ.2010.022].
Immunity properties of the s-degrees
SORBI, ANDREA
2010-01-01
Abstract
We investigate immunity properties of the s-degrees. In particular we show that neither the immune nor the hyperimmune s-degrees are upwards closed since there exist $\Delta^0_2$ s-degrees $a \leq_s b$ such that $a$ is hyperimmune, but $b$ is immune free. We also show that there is no hyperhyperimmune $\Pi^0_2$ set A such that $\overline{K} \leq_{\overline{s}} A$, where $\overline{K}$ is the complement of the halting set and $ \leq_{\overline{s}}$ denotes the finite-branch version of s-reducibility.File | Dimensione | Formato | |
---|---|---|---|
GMJ.2010.022.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
323.69 kB
Formato
Adobe PDF
|
323.69 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/17578