recursive and creative theorem

204 Views Asked by At

How can we show that if A is creative, then A is not recursive.

Only thing I can get out is the fact that if A is creative, if it is rec. enumerable and the complement(A) is productive.

Thanks

1

There are 1 best solutions below

0
On BEST ANSWER

If $A$ is recursive, then the complement($A$) is r.e., let it be $W_{e}$.

According to de definition of the productive set, there is a recsive function $f(x)$ such that:

$W_{x}\subseteq \overline{A}\Longrightarrow (f(x)\downarrow\wedge f(x)\in\overline{A}-W_{x})$

The contradiction is quite straightforward: $W_{e}\subseteq \overline{A}$ but $\overline{A}-W_{e}=\emptyset$.