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.

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}$.

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).