Codes for sets

If $\chi(n, x)$ is the computable function deciding $x \in A_n$, the parameter form of SMN gives a computable $h$ with $\Phi_{h(n)}(x) = \chi(n, x)$. Conversely, if $h$ is computable and each $h(n)$ is a $\Delta^0_1$ index of $A_n$, then $\chi(n, x) = \Phi_{h(n)}(x)$ is computable by the universal function, and total. The c.e. case is the same, with domains in place of characteristic functions.

$x \in D_n$ if and only if the binary digit of $n$ at position $x$ is $1$, that is, $\lfloor n / 2^x \rfloor$ is odd; and all elements of $D_n$ are smaller than $n + 1$, so the other relations are obtained by bounded quantification over $x \leq n$. The indices are obtained by the parameter form of SMN, applied to the computable functions $(n, x) \mapsto D_n(x)$ and to the partial function that converges on $(n, x)$ exactly when $x \in D_n$.

Suppose $f$ exists. By Corollary 5.2 of “Kleene's fixed point theorem”, there is $e$ such that $\Phi_e(x)$ converges if and only if $x = 0$, $f(e)\converge$, and $\Phi_{f(e)}(0)\converge = 0$; the description is uniform in $e$, since $f$ and the universal function are partial computable. Then $W_e$ is $\{0\}$ or $\emptyset$, hence computable, so $f(e)\converge$ and $\Phi_{f(e)}$ is the characteristic function of $W_e$. If $\Phi_{f(e)}(0) = 0$, then $0 \in W_e$ by construction, while the characteristic function says $0 \notin W_e$. If $\Phi_{f(e)}(0) = 1$, then $W_e = \emptyset$, while the characteristic function says $0 \in W_e$. Both cases are contradictory.

Suppose $f = \Phi_c$ exists. By Corollary 5.2 of “Kleene's fixed point theorem”, there is $e$ such that for every $t$,

The conditions are decidable for each $t$, so $\Phi_e$ is total, with values in $\{0, 1\}$, and it is the characteristic function of a set $F$ with at most one element. So $e$ is a $\Delta^0_1$ index of a finite set, and $f(e)\converge = |F|$. If $f(e) = 0$, then $F$ contains the stage at which $f(e)$ converges, and $|F| = 1$. If $f(e) \geq 1$, then $F = \emptyset$ and $|F| = 0$. Both cases contradict $f(e) = |F|$.

The proof of Fixed point theorem uses only the universal function and the SMN theorem, which hold for oracle machines uniformly in the oracle (Relativized universal function and Relativized SMN theorem). The same construction, with the functions $d$ and $f \circ d$ computable and independent of the oracle, gives a fixed point valid for every oracle. The second statement follows as Corollary 5.2 of “Kleene's fixed point theorem” follows from the theorem.

Suppose $f$ exists. By Theorem 3.2 of “The Turing jump” applied to the uniformly $X$-c.e. set $\{ 0 : X \neq \emptyset \}$, there is $b$ such that $b \in X' \iff X \neq \emptyset$ for every $X$. By Lemma 5.6, there is $e$ such that for every oracle $Z$ and every $t$,

With $Z = \emptyset'$, the function $\Phi^{\emptyset'}_e$ is total with values in $\{0, 1\}$; let $A$ be the set it computes. By monotonicity of stages, once the condition holds at some $t$, it holds at all larger $t$. So $A$ is empty or cofinite, hence computable and low, and $e$ is a $\Delta^0_2$ index of it. Hence $i = f(e)$ is defined and is a lowness index of $A$: $\Phi^{\emptyset'}_i(b) = A'(b)$, and $A'(b) = 1$ if and only if $A \neq \emptyset$. If $\Phi^{\emptyset'}_i(b) = 0$, then the condition holds for all large $t$, so $A \neq \emptyset$ and $A'(b) = 1$. If $\Phi^{\emptyset'}_i(b) = 1$, the condition never holds, so $A = \emptyset$ and $A'(b) = 0$. Both cases are contradictory.