# Show that $x \in W_{x}$ is undecidable

The Cutland's book called Computability has a theorem whose proof i don't understand and i have developed another simpler proof. Could you tell me if this proof is correct?

DEFINITION 1: $$\phi_{x}, x \in \mathbb{N}$$, is a partial computable function.

DEFINITION 2: $$W_{x}$$ is de domain of the partial computable function $$\phi_{x}$$.

THEOREM 1: $$x \in W_{x}$$ or, equivalently, $$\phi_{x}(x)$$ is defined, is undecidable.

PROOF: Let f: $$\mathbb{N} \rightarrow$$ {0, 1} the characteristic function defined as: $$f(x)=\begin{cases} 1 & \text{ if } x \in dom(\phi_{x})\\ 0 & \text{ if } x \notin dom(\phi_{x}) \end{cases}$$

We assume that $$f(x)$$ is a partial computable function $$\Leftrightarrow \exists i \in \mathbb{N}, f = \phi_{i}$$

Then,

$$\phi_{i}(x)=f(x)=\begin{cases} 1 & \text{ if } x \in dom(\phi_{x})\\ 0 & \text{ if } x \notin dom(\phi_{x}) \end{cases}$$

If x = i then,

$$\phi_{i}(i)=\begin{cases} 1 & \text{ if } i \in dom(\phi_{i})\\ 0 & \text{ if } i \notin dom(\phi_{i}) \end{cases}$$

But, $$\phi_{i}(i)=0$$ if $$i \notin dom(\phi_{i})$$ is a contradiction because $$\phi_{i}(i)$$ is undefined $$\Rightarrow f$$ is not computable $$\Rightarrow$$ The THEOREM 1 is shown.

This doesn't work. $$\phi_i(i)$$ will just be $$1$$ -- no contradiction here ($$\phi_i$$ is a total function by assumption).

Let $$f$$ decide $$x \in W_x$$. Let $$g$$ be the partial computational function such that $$g$$, on input $$x$$, holds (with value $$0$$, say) iff and only if $$f(x) = 0$$. (1)
Let $$m < \omega$$ be such that $$g = \phi_m$$. Then $$m \in W_m \iff \phi_m(m) \text{ holds } \iff f(m) = 0 \iff m \not \in W_m.$$ Contradiction!
(1) Such a $$g$$ exists: E.g. $$g$$, on input $$x$$, will compute $$f(x)$$. If $$f(x) = 0$$, it will hold with value $$0$$. Otherwise, it will go into an infinite loop. (As you can tell, I picture my computable functions as Turing machines.)
• @Carlos Your updated proof still doesn't work. You should think carefully through both cases and study the proof that I've suggested: As far as I can see, there's no way to derive a contradiction directly from $f$ -- you need some other partially computable function that wraps $f$ into a diagonal argument like I did. – Stefan Mesken Feb 15 '19 at 10:56