Prove $A$ is creative set

133 Views Asked by At

Let $\varphi_i$ be the $i$-th partial function of our enumeration. Consider the set $$ A = \{ y \in \mathbb{N} \mid \varphi_{\mathrm{fact}(y)}(y) \downarrow \} $$ I have to prove this set to be creative. $A$ is recursively enumerable because its semi-characteristic function can be implemented through the algorithm:

function is_element_in_a(y):
    u = fact(y)
    if varphi_u(y) terminates then
        output(true)
    end

Then, $A$ is creative because its complement $\bar{A}$ is a productive set. We can prove $\bar{A}$ to be productive through many-one reduction: $$ \{ x \mid \varphi_x(x) \uparrow \} = \bar{K} \preceq \bar{A} $$ $$ \bar{K} \preceq \bar{A} \iff K \preceq A \iff \left( \exists h \text{ total function such that } x \in K \iff h(x) \in A \right) $$ How can I prove this?

My attempt

Consider the partial recursive function $$ \psi(x,y) = \begin{cases} 1, x \in K \\ \uparrow, \text{otherwise} \end{cases}$$ which can be specialized through the s-m-n theorem to the function $$ \forall y \quad \varphi_{h(x)}(y) = \psi(x,y) \text{ for fixed } x $$ where $h$ is a total recursive function. Then \begin{align*} x \in K & \to \varphi_{h(x)}(\,\cdot\,) \downarrow \; = 1 & x \not\in K & \to \varphi_{h(x)}(\,\cdot\,) \uparrow \\ & \to \varphi_{\mathrm{fact}(\mathrm{fact}^{-1}(h(x)))}(\,\cdot\,) \downarrow & & \to \varphi_{\mathrm{fact}(\mathrm{fact}^{-1}(h(x)))}(\,\cdot\,) \uparrow \\ & \to \varphi_{\mathrm{fact}(\mathrm{fact}^{-1}(h(x)))}(\mathrm{fact}^{-1}(g(x))) \downarrow & & \to \varphi_{\mathrm{fact}(\mathrm{fact}^{-1}(h(x)))}(\mathrm{fact}^{-1}(g(x))) \uparrow \\ & \to \mathrm{fact}^{-1}(h(x)) \in A & & \to \mathrm{fact}^{-1}(h(x)) \not\in A \end{align*}

but I'm not really sure I can use $\mathrm{fact}^{-1}$ like that because factorial is not bijective function ($\mathrm{fact}^{-1}(y)$ may not exists).