A $wtt$-introimmune set in \texorpdfstring{$Π^0_1$}{Pi01} and introimmunity for several reducibilities
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912971939119104 |
|---|---|
| author | Cintioli, Patrizio |
| author_facet | Cintioli, Patrizio |
| contents | We prove that there exists a weak truth-table introimmune set in the class $Π^0_1$, settling the question left open in previous work of whether the known $Δ^0_2$ existence result can be improved to $Π^0_1$. Since $Σ^0_1$ sets cannot be immune, this is best possible for weak truth-table introimmunity. We also study introimmunity for Jockusch's bounded-search reducibility $\le_{bs}$ and Andersen's Dartmouth reducibility $\le_D$, proving the existence of $Δ^0_2$ sets that are $bs$-introimmune and $D$-introimmune; hence there also exists a $Δ^0_2$ $D^+$-introimmune set. We next consider the classical reducibility $\le_Q$, which is not contained in $\le_T$ on all subsets of $ω$. We show that no infinite $Π^0_1$ set is $Q$-introimmune, while a $Δ^0_2$ $Q$-introimmune set does exist. Thus the existence of $Δ^0_2$ $Q$-introimmune sets is best possible within the arithmetical hierarchy. Finally, for enumeration reducibility $\le_e$, we show that no infinite $Π^1_1$ set is $e$-introimmune, although $e$-introimmune sets do exist in the unrestricted sense. The proofs combine finite-injury priority arguments with dynamic spacing methods for $\le_{wtt}$, $\le_{bs}$, and $\le_D$, a bit-by-bit finite-extension construction for $\le_Q$, and an application of Soare's abstract existence theorem in the enumeration case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14264 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A $wtt$-introimmune set in \texorpdfstring{$Π^0_1$}{Pi01} and introimmunity for several reducibilities Cintioli, Patrizio Logic 03D30 We prove that there exists a weak truth-table introimmune set in the class $Π^0_1$, settling the question left open in previous work of whether the known $Δ^0_2$ existence result can be improved to $Π^0_1$. Since $Σ^0_1$ sets cannot be immune, this is best possible for weak truth-table introimmunity. We also study introimmunity for Jockusch's bounded-search reducibility $\le_{bs}$ and Andersen's Dartmouth reducibility $\le_D$, proving the existence of $Δ^0_2$ sets that are $bs$-introimmune and $D$-introimmune; hence there also exists a $Δ^0_2$ $D^+$-introimmune set. We next consider the classical reducibility $\le_Q$, which is not contained in $\le_T$ on all subsets of $ω$. We show that no infinite $Π^0_1$ set is $Q$-introimmune, while a $Δ^0_2$ $Q$-introimmune set does exist. Thus the existence of $Δ^0_2$ $Q$-introimmune sets is best possible within the arithmetical hierarchy. Finally, for enumeration reducibility $\le_e$, we show that no infinite $Π^1_1$ set is $e$-introimmune, although $e$-introimmune sets do exist in the unrestricted sense. The proofs combine finite-injury priority arguments with dynamic spacing methods for $\le_{wtt}$, $\le_{bs}$, and $\le_D$, a bit-by-bit finite-extension construction for $\le_Q$, and an application of Soare's abstract existence theorem in the enumeration case. |
| title | A $wtt$-introimmune set in \texorpdfstring{$Π^0_1$}{Pi01} and introimmunity for several reducibilities |
| topic | Logic 03D30 |
| url | https://arxiv.org/abs/2603.14264 |