Given a reducibility $\leq_\mathrm{r}$, we say that an infinite set $A$ is $r$-introimmune if $A$ is not $r$-reducible to any of its subsets $B$ with $|A\backslash B|=\infty$. We consider the many-one reducibility $\leq_\mathrm{m}$ and we prove the existence of a low$_1$ $m$-introimmune set in $\Pi^0_1$ and the existence of a low$_1$ bi-$m$-introimmune set.
Low sets without subsets of higher many-one degree
CINTIOLI, Patrizio
2011-01-01
Abstract
Given a reducibility $\leq_\mathrm{r}$, we say that an infinite set $A$ is $r$-introimmune if $A$ is not $r$-reducible to any of its subsets $B$ with $|A\backslash B|=\infty$. We consider the many-one reducibility $\leq_\mathrm{m}$ and we prove the existence of a low$_1$ $m$-introimmune set in $\Pi^0_1$ and the existence of a low$_1$ bi-$m$-introimmune set.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
