Prove that a set is recursively enumerable using Kleene recursion theorem.

Question

Hello I am having difficulties proving that a set is or isn't recursively enumerable using KRT.

For example a set $D = \{p : W_p = \{0\}\}$. How can I prove that this set is not r.e using KRT?

Answer 1

Hint: Assume $D$ is r.e. and use the recursion theorem to find $e \in \mathbb{N}$ with $$ \varphi_e(y) = \begin{cases} 0,& \text{if } y = 0,\\ 0,& \text{if } (y > 0) \wedge (e \in D),\\ \uparrow,& \text{otherwise}. \end{cases} $$ What can you say about $e \in D$?

Update. There are other ways to show that this set is not r.e., Kleene's recursion theorem is just one of them. Another way is to use reduction and to show that $\overline{K} \leqslant_m D$. Indeed, consider the following function $f(x)$ with $$ \varphi_{f(x)}(y) = \begin{cases} 0,& \text{if } y = 0,\\ 0,& \text{if } (y > 0) \wedge (x \in K)\\ \uparrow,& \text{otherwise.} \end{cases} $$ We have $x \notin K \Leftrightarrow f(x) \in D$, hence $\overline{K} \leqslant_m D$ and since $\overline{K}$ is not r.e. so is $D$.

As I see it, the recursion theorem allows to define a function by self-reference, and self-reference is known to be a source of many paradoxes and contradictions. That's why the recursion theorem often can be used to prove that some set is not r.e. or some function can't be total or computable by contradiction.

However, the are a lot of "positive" applications of the recursion theorem (as opposed to showing that something does not exist by contradiction), for example, it is used in standard proofs of "creativeness implies $m$-completeness" or "Kleene's $\mathcal{O}$ is a universal system of ordinal notations". You can find more examples in Chapter 11 of "Theory of recursive functions and effective computability" by H. Rogers.