Proving Rice's theorem using Kleene's fixed point theorem

Question

Here's Rice's theorem from recursion theory:

Let $\mathscr F$ be the class of all unary computable functions. Let $\mathscr A\subset \mathscr F$ be an arbitrary nontrivial property of computable functions ('nontrivial' means that there are both functions satisfying the property and functions not satisfying it). Let $U$ Be a Godel universal function (the definition can be found here). Then $\{n:U_n\in\mathscr A\}$ is undecidable. ($U_n(x)$ is the $n$th section of the Godel universal function $U(n,x)$)

I know how to prove it by $m$-reducing $K$ (the set of all programs that halt on themselves) to $\{n:U_n\in\mathscr A\}$. I've also found a proof through Kleene's (?) fixed point theorem (in some lecture notes, so there may be mistakes), and I have a question about that proof and even about the statement (it slightly differs from the above):

Statement. If $\mathscr A$ is a nontrivial property of programs (two programs compute the same function $\implies$ both programs either satisfy the property or do not satisfy it), then the set of all programs possessing this property is undecidable.

So the first question, is it okay that this statement doesn't mention 'Godel universal function'? I think the proof through $m$-reducibility uses the fact that $U$ is a Godel universal function.

Proof. Assume $\mathscr A$ is decidable. Since $\mathscr A$ is nontrivial, there are $p\in \mathscr A$, $q\in\overline{\mathscr A}$. Consider the transformation of programs $$h:x\mapsto q\text{ if } x\in \mathscr A\\ x\mapsto p \text{ if } x\notin \mathscr A$$ If $\mathscr A$ is decidable, then $h$ is computable. Then by the fixed point theorem, $h$ has a fixed point $t$. Now if $t\in\mathscr A$ then $h(t)=q\notin\mathscr A$. But $t$ and $h(t)$ both either lie in $\mathscr A$ or do not lie in $\mathscr A$ (by the condition in the statement of the theorem). This is a contradiction. Similarly, if $t\notin A$, we get a contradiction.

I don't see how this proof uses that $t$ is a fixed point. Doesn't this directly imply that $t=h(t)$, and if $t\in \mathscr A$ then the fact that $t=h(t)=q\notin\mathscr A$ gives a contradiction without using that condition from the statement?

Moreover, the first version of the theorem doesn't mention anything about this property ('two programs compute the same function $\implies$ both programs either satisfy the property or do not satisfy it'), do we even need it?

Answer 1

Let us first consider the following two statements:

1. Let F be the class of all unary computable functions. Let $A \subseteq F$ be an arbitrary nontrivial property of computable functions ('nontrivial' means that there are both functions satisfying the property and functions not satisfying it) and $U$ be a Godel universal function. Then $\{n:U_n \in A\}$ is undecidable.

2. If $B$ is a nontrivial property of programs (two programs compute the same function ⟹ both programs either satisfy the property or do not satisfy it), then the set of all programs possessing this property is undecidable.

To show that these are equivalent, it suffices to reduce deciding $A$ to deciding $B$ and vice versa. Let $w$ be a computable function that takes as input some $n$ and outputs a program computing $U_n$.

Given a nontrivial $A \subseteq F$, we define $B$ to be the set of all programs $p$ s.t. the function computed by $p$ is in $A$. Clearly, $B$ is nontrivial and depends only on the function computed by the program. Then $U_n \in A$ iff $w(n) \in B$.

Given a nontrivial property $B$ of programs which depends only on their corresponding functions, define $A = \{f : $ there is a program $p$ s.t. $p$ computes $f$ and $p \in B\}$. Clearly, $A$ is nontrivial. Now let $\phi$ be a partial computable function with domain a subset of $\mathbb{N}^2$ s.t. $\phi(p, n)$ computes $p(n)$. Then let $s$ be the total computable function s.t. $phi(p, n) = U(s(p), n)$ for all $p$, $n$. Then we have $p \in B$ iff $U_{s(p)} \in A$.

Thus, statements 1 and 2 are equivalent.

Now on to your primary question.

The statement "$h$ has fixed point $t$" actually means the following: the program $t$ and the program $h(t)$ compute the same function. It does not mean that $t = h(t)$.

To be very formal, a "program" is a natural number, and there is a special partial computable function $\phi$ which takes two inputs $p$ and $n$ that has the following property: for every computable function $f$ there exists $p$ s.t. for all $n$, $\phi(p, n) = f(n)$.

The fact that "$t$ is a fixed point of $h$" actually means nothing more than that for all $n$, $\phi(t, n) = \phi(h(t), n)$.

Obviously, if one interpreted "fixed point t" as $h(t) = t$, than the function $f(x) = x + 1$ couldn't have a fixed point. This contradicts Kleene's theorem.