Proving that $\{x|\varphi_x \; \text{is extendible to a total computable function} \} \neq \omega$ 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.
 A: 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! 
A: A variant: Let $f(i)$ be the number of steps Turing machine number $i$ takes to stop on an empty tape, or undefined if Turing machine number $i$ doesn't stop. That is clearly a partial computable function. But there can be no total computable function $g$ that extends $f$ (that is, such that $g(i)=f(i)$ whenever $f(i)$ is defined). Namely, if such a $g$ existed, we could decide the halting problem simply by running a given machine for $g(i)$ steps and see whether it stops by then or not.
Therefore the index of $f$ in the sequence of all partial computable functions is not a member of $\mathrm{Ext}$.
A: The definition of a pair of recursively inseparable r.e. sets is virtually identical to the definition of a partial function that cannot be extended to a total function. Consider on one hand the sets $A,B$, and on the other hand the function $f$ defined so that $f(n) = 0$ if $n \in A$, $f(n) = 1$ if $n \in B$ (or just $f(n) \downarrow\not = 0$ if $n \in B$), and $f$ is undefined otherwise. Then $f$ is computable if and only if $A$ and $B$ are r.e., and any extension of $f$ to a total function gives a recursive set $C = f^{-1}(0)$ with $A \subseteq C$ and $C \cap B = \emptyset$, and any such $C$ gives an extension of $f$ to a total function.  It's all just rearranging synonyms. 
