User:IssaRice/Computability and logic/K is recursively enumerable: Difference between revisions

Revision as of 20:02, 9 January 2019

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

Proofs

Finding a partial recursive function that enumerates K

This proof is from Enderton.^[1]

Let $ϕ_{0}, ϕ_{1}, ϕ_{2}, \dots$ be a standard enumeration of the partial recursive functions.

We can define the diagonal partial function $d (x) : = ϕ_{x} (x) + 1$ . This is a partial recursive function because both $ϕ_{x}$ and $x \mapsto x + 1$ are, and we can obtain $d$ via substitution. Thus, $d = ϕ_{e}$ for some $e \in N$ .

But now $K = d o m a i n d = d o m a i n ϕ_{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.

Using programs

References

↑ Herbert Enderton. Computability Theory. p. 80

[1] Herbert Enderton. Computability Theory. p. 80

[1]

@@ Line 11: / Line 11: @@
 We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.
-But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.
+But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.
 ===Using programs===