An indirect proof of Rice's theorem

Question

I'd like to deduce a proof of this version of Rice's theorem from the Kleene theorem. (I've asked a similar question before but this one is different.)

Let $\mathcal F$ be the class of all unary computable functions. Let $\mathcal A\subset \mathcal F$ be a proper subset. Let $U$ be a Godel universal function (the definition can be found here). Then $\{n:U_n\in\mathcal A\}$ is undecidable. ($U_n(x)$ is the $n$th section of the Godel universal function $U(n,x)$)

Here's my attempt:

Let $T=\{n:U_n\in\mathcal A \}$. Let $f\in\mathcal A$ and $g\notin \mathcal A$. Define $$h:N\to N\\ $$ by $$n\mapsto f(n)\text{ if } n\in T\\ n\mapsto g(n)\text{ if } n\notin T\\ $$

(this is the only reasonable thing I can think of). Assume $T$ is decidable. Then $h$ is a total computable function. Thus by Kleene's theorem, there is a number $n_0$ such that $$U(n_0,x)=U(h(n_0),x)$$ for all $x$.

But I'm not sure what to do next. One option is to consider cases $n_0\in T$ and $n_0\notin T$. Well, suppose $n_0\in T$. Then $h(n_0)=f(n_0)$. I don't know what to do to get a contradiction. I could express $f$ in terms of $U$: suppose $n_f$ is the number of the computable function $f$, i.e. $U(n_f,x)=f(x)$ for all $x$. Then $h(n_0)=U(n_f,n_0)$. What to do next? What kind of contradiction should I be trying to obtain?

Answer 1

Since $\mathcal A$ is proper, we can take $U_p\in \mathcal A$ and $U_q\notin \mathcal A$. Define $$h:N\to N$$ by $$n\mapsto q \text{ if } n\in T\\n\mapsto p\text{ if }n\notin T$$ Assume $T$ is decidable. Then $h$ is computable. Let's show that $h$ cannot have a fixed point.

Suppose $n$ is a fixed point. So $U(n,x)=U(h(n),x)$ for all $x$.

• Case 1: $n\in T$. Then $U(n,x)=U(q,x)$ for all $x$, i.e. $U_n=U_q$. This is impossible because $U_n\in \mathcal A$ but $U_q\notin \mathcal A$.
• Case 2: $n\notin T$. Then $U(n,x)=U(p,x)$ for all $x$, i.e. $U_n=U_p$. This is impossible for a reason similar to the reason above.

So $h$ cannot have a fixed point. Thus $T$ is undecidable.