We consider the weak truth-table reducibility $le_{wtt}$ and we prove the existence of $wtt$-introimmune sets in $Delta^0_2$. This closes the gap on the existence of arithmetical $r$-introimmune sets for all the known reducibilities $le_r$ strictly contained in the Turing reducibility.
Sets with no subsets of higher weak truth-table degree
Patrizio Cintioli
2018-01-01
Abstract
We consider the weak truth-table reducibility $le_{wtt}$ and we prove the existence of $wtt$-introimmune sets in $Delta^0_2$. This closes the gap on the existence of arithmetical $r$-introimmune sets for all the known reducibilities $le_r$ strictly contained in the Turing reducibility.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
sets with no subsets of higher weak truth-table degree.pdf
accesso aperto
Descrizione: articolo
Tipologia:
Versione Editoriale
Licenza:
DRM non definito
Dimensione
438.02 kB
Formato
Adobe PDF
|
438.02 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
