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$. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that $K$ is recursively enumerable.