The problem that I'm working on is to prove that
$$ Ext=\{ x \ | \ \varphi_x \text{is extendible to a total computable function}\} $$
is not equal to $\omega$. Here $\varphi_x$ is the $x$-th partial computable function. I'm having problem understanding what $Ext$ is. Does it mean that if $x \in Ext$ then $x$ is in some $W_i \subset W_j$ where $W_j$ is computable? But doesn't that mean $W_i$ is also computable?
More on the context of this problem, this is part 2 of a problem from Soare's book. Part 1 is to prove that there exists computably inseparable r.e. set, which I did.
Best Answer
The proof that $\text{Ext} \neq \omega$ is given below. However, to address you qustion, $\text{Ext}$ is just the set of $i$ such that $\varphi_i(x)$, which may not be total can be extending to a total computable function $\varphi_j$ such that for all $x$ such that $\varphi_i(x)\downarrow$, $\varphi_j(x) \downarrow = \varphi_i(x)$.
Also it is not true that $i \in \text{Ext}$ if there is a $j$ such that $W_i \subset W_j$ and $W_j$ is computable. For example, every $W_i$ is a subset of $\omega$, which is computable. This would imply $\text{Ext} = \omega$, which you are asked to prove is not the case.
Also, you said that $W_i \subset W_j$ where $W_j$ is computable implies $W_i$ is computable. Again, every c.e. set is a subset of $\omega$ which is computable. If your statement was true then every set would be computable. Clearly, $K$ the halting problem is not.
By the enumeration theorem, there exists a index $z$ such that
$\varphi_z(e,x) = \varphi_e(x)$
That is, $z$ is the index for the universal function.
Let $k$ be the index of the following partial computable function.
$\varphi_k(x) = \varphi_z(x,x)$
The claim is that $k \notin \text{Ext}$. Suppose $k \in \text{Ext}$, this would imply that $\varphi_k$ can be extended to a total computable function $\varphi'(x)$. Now define the computable function $\theta$ as follow :
$\theta(x) = \varphi'(x) + 1$
Clearly $\theta$ is a partial (actually total) computable function. Therefore, it has an index. However, it can not be $\varphi_x$ for any any $x$. This is because if $\varphi_x(x)$ converges, then $\theta(x) = \varphi'(x) + 1 = \varphi_z(x,x) + 1 = \varphi_x(x) + 1 \neq \varphi_x(x)$. If $\varphi_x(x)$ does not coverges, then it can not be equal to $\theta(x)$ since $\theta$ is a total computable function. $\theta \neq \varphi_x$. Contradiction since $\theta$ has no index. Thus $k \notin \text{Ext}$. $\text{Ext} \neq \omega$.
At least in Soare's new book, he asks this question twice. The second you are mean to use the computably inseparable thing. If I can remember how to do it that way I will post a proof later.
Here is the proof of the result using the computably inseparable pair. Recall that $A$ and $B$ are computably inseparable if there does not exists a computable set $C$ such that $A \subset C$ and $A \cap C = \emptyset$. I assumed that you proved already that there exists an inseparable pair $A$ and $B$, where $A$ and $B$ are c.e.
Define
$\psi(x) = \begin{cases} 1 & \quad x \in A \\ 0 & \quad x \in B \end{cases}$
This function partial computable (it diverges if $x$ is in neither). Therefore, this function $\psi$ has an index, say $e$. Assuming $\text{Ext} = \omega$, $\varphi_e$ can be extended to a total computable function $\varphi_f$. Since $\varphi_f$ is total and $0,1$ valued, let $C$ be $\{x : \varphi_f(x) = 1\}$, which is computable since $\varphi_f$ is total. Clearly, $A \subset C$ since $\varphi_f(x) = 1$ whenever $\varphi_e(x) = 1$ and $\varphi_e(x) = 1$ if and only if $x \in A$. Similarly, $A \cap C = \emptyset$ since $\varphi_f(x) = 0$ if $\varphi_e(x) = 0$ and $\varphi_e(x) = 0$ if and only if $x \in B$. Thus $C$ contradict that fact that $A$ and $B$ are computable inseparable. Contradiction!