the set of extendable p.c. functions is not N

Question

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$.

Would be grateful for your help.

Answer 1

HINT: have you heard of recursively inseparable sets? If $A, B$ are r.e. and disjoint, there's a natural partial computable function $f$ given by $f(x)=0$ for $x\in A$, $f(x)=1$ for $x\in B$, and $f(x)\uparrow$ for $x\not\in A\cup B$.

• Suppose $f$ can be extended to a total recursive function. Show that there is a recursive set $C$ with $A\subseteq C$ and $C\cap B=\emptyset$ (such a $C$ is a separator for $A$ and $B$).

• Show that there is a pair of disjoint r.e. sets $A$ and $B$ which are recursively inseparable (that is, no such $C$ exists). HINT$^2$: consider the theorems of Peano arithmetic . . .

---

This is merely one approach. Another approach comes via diagonalization.

Consider the following function $g$: $g(x)=\varphi_x(x)+1$. Intuitively, $g$ should diagonalize out of the set of partial recursive functions. Unfortunately, of course, there's no reason we can't have $g=\varphi_x$ for some $x$ - all that we'd need is $\varphi_x(x)\uparrow$.

Do you see why this $g$ can't be extended to a total computable function?