Showing a set is immune (has no infinte r.e. subset)

110 Views Asked by At

Consider the set $SD = \{ e : \phi_e(0) \downarrow \wedge \forall j < e (\phi_j(0) \neq \phi_e(0) )\}$

Show that $SD$ has no infinite recursively enumerable subset.

I think the idea is to use the recursion theorem somehow to get a contradiction. We want to be able to set $\phi_e(0)$ so that we can get $\phi_e(0) = \phi_i(0)$ for some $i$ greater than $e$.

1

There are 1 best solutions below

0
On

It is sufficient to show that $SD$ contains no infinite recursive subset $R \subseteq SD$. Assume there is such a subset $R$. Using recursion theorem define the following function $$ \varphi_e(x) = \begin{cases} \uparrow,& \text{if } e \in R,\\ \varphi_n(x),& \text{where } n = \mu t(t \in R \wedge t > e), \text{ if } e \notin R. \end{cases} $$

If $e \in R \subseteq SD$, then $\varphi_e(0)\!\uparrow$ and hence $e \notin SD$, a contradiction. It means $e \notin R$, but in this case $\varphi_e(0) = \varphi_t(0)\!\downarrow$ for some $t \in R \subseteq SD$ and $t > e$, contradicting $t \in SD$.