Showing the class of all recursive sets is recursively enumerable.

153 Views Asked by At

Correct?

Proof:

Let D = {$A_i$ |$A_i$ is a recursive set$\}$. Take $z \in D$. Thus $z = A_i$ for some $i\in N$.

Then: $\exists{f}$ such that for any choice of $A_i$ $\in$ D:

$f(x) = 1$ if $x \in A_i$ and $f(x) = \emptyset$ otherwise.

We call each such $f$ an $f_i$ as it gives a decision procedure for $A_i$.

We now show that $D$ has a semi-decision procedure, and therefore is R.E. (recursively enumerable). We define $g$ on $D$ as follows:

$g(x) = 1$ if $f_i(x) = 1$ for some $A_i$ $\in$ D & $g(x)$ = undefined otherwise.

We show that D can under no circumstances be recursive.

Subproof: Suppose D were recursive for a contradiction, symbolized by $\bot$. Then

$\Rightarrow$ D has a decision procedure

$\Rightarrow$ The complement of D, say D`, is recursive (and so has a decision procedure)

$\Rightarrow$ D` $\in$ D (By the definition of D)

$\Rightarrow$ D` = $A_i$ for some $A_i$ $\in$ D.

$\Rightarrow$ But D` $\neq$ $A_i$ for every $A_i$ (by definition of complement of D)

$\Rightarrow$ $\bot$.

END SUBPROOF.

END PROOF.