Creative and Simple Set and $S \leq_m C$?

Question

I see in an old-exam that wrote if C is a Creative Set and S be a Simple Set we have:

$S \leq_m C$ (i.e. m: many to one reducible ).

How we can conclude this?

Answer 1

Let $\phi_i$ be an acceptable programming system. This is a set of all recursive (computable) partial functions from $\mathbb N$ to $\mathbb N$. Note that to be able to use several input arguments, we consider a trivial bijection from $\mathbb N^k$ to $\mathbb N$ that we note $(x_1,x_2,\dots,x_k)$

We note $\phi_n(x)\downarrow$, if the computation of $\phi_n$ on input $x$ halts. Otherwise we note $\phi_n(x)\uparrow$ to mean it doesn't halt.

We note $W_n=\{x\,|\,\phi_n(x)\downarrow\}$, the domain of $\phi_n$

$S$ is a simple set implies that $S=W_s$ for some $s\in\mathbb N$.

$C$ is creative implies that its complement $\overline{C}$ is productive. Hence there is a recursive total function $f_c$ such that $$W_n\subseteq\overline{C}\Rightarrow \big(f_c(n)\notin C\wedge f_c(n)\notin W_n\big) $$

Then $C$ will be $1$-complete (and so $m$-complete), which means $$\forall n\; W_n\le_1 C $$

So we don't really need the fact that $S$ is simple, only the fact that $S$ is recursively enumerable.

Proof

By $snm$ theorem, we define a total recursive injective function $s(x,y)$ such that $$\phi_{s(x,y)}=\mbox{if }\phi_n(y)\downarrow\wedge\; f_c(x)=z\mbox{ then }\downarrow\mbox{ else }\uparrow $$

Hence if $y\in W_n$, $W_{s(x,y)}$ is the singleton $f_c(x)$ else it's the empty set.

Using generalised Kleene's fixed point theorem, there is a recursive total injective function $h$ such that $$\forall y \;\phi_{h(y)}=\phi_{s(h(y),y)}$$ It means that both function with index $h(y)$ and index $s(h(y),y)$ computes the same thing.

Now we can claim that $W_n\le_1 C$ by function $f_c\circ h$ :

1. if $y\in W_n$, then $W_{h(y)}$ is the singleton $f_c(h(y))$. But if $f_c(h(y))\notin C$, then using the properties of $f_c$, we deduce that $f_c(h(y))\notin W_{h(y)}$ : a contradiction. So $f_c(h(y))\in C$
2. if $y\notin W_,$, then $W_{h(y)}$ is the empty set. We use again the properties of $f_c$ to claim that $f_c(h(y))\notin C$.