User:IssaRice/Computability and logic/K is recursively enumerable

$K:=\{x:x\in W_x\}$

Proofs

Finding a partial recursive function that enumerates K

This proof is from Enderton.

Proof. Let ${\varphi }_0,{\varphi }_1,{\varphi }_2,\dots$ be a standard enumeration of the partial recursive functions.

We can define the diagonal partial function $d(x):={\varphi }_x(x)+1$. This is a partial recursive function because both ${\varphi }_x$ and $x\mapsto x+1$ are, and we can obtain $d$ via substitution. Thus, $d={\varphi }_e$ for some $e\in \mathbf{N}$. (Actually, is it really so simple to show $d$ is partial recursive? We're not just using a fixed ${\varphi }_x$, but rather we are allowing the partial function index to move around. To be more rigorous, I think we need to say that ${\varphi }_x(x)=\mathrm{\Phi }(x,x)$, where $\mathrm{\Phi }$ is the two-place universal function. Since the universal function is partial recursive, we can be sure that we can use the expression "${\varphi }_x(x)$" and move the index around. Even more formally, we can say $d=\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}(\mathrm{\Phi };{\mathrm{i}\mathrm{d}}_1^1,{\mathrm{i}\mathrm{d}}_1^1)$.)

But now $K=\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}d=\mathrm{d}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}{\varphi }_e=W_e$. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that $K$ is recursively enumerable.

Discussion. The definition of $d$ doesn't seem to be important. Actually, I think we can just take $d(x)={\varphi }_x(x)$. But it seems Enderton did the plus one to make a further point (namely, that it looks like we might be diagonalizing out of this class of functions, but luckily we're not, thanks to our objects only being partial functions).

Using programs

Peter Smith. An Introduction to Gödel's Theorems. p. 24.