Prove that EXT,TOT and INF are not recursively enumerable

Question

I am currently working on the reduction method to demonstrate that a set is not recursively enumerable but I am struggling to find suitable functions for the reductions. In particular I have started working on the proving that the EXT set is not r.e.:

$$ EXT=\{x|\phi_x \text{ is extensible to a total recursive function}\} $$

My intuition leads me to try and find a reduction from $\overline{K}$to EXT by defining a function like this: $$ f(x)=\left\{\begin{matrix} \text{extensible function} \quad \text{if } x \epsilon \overline{K} \\ \text{non-extensible function} \quad \text{if } x\epsilon K \end{matrix}\right. $$

by using an already total function as the extensible function (it is already total so it should also be extensible to total) and, for the non-extensible function something like this:

$$ g(x)=\left\{\begin{matrix} x \quad \text{if } x \epsilon K \\ \uparrow \quad \text{if } x\epsilon \overline{K} \end{matrix}\right. $$

which cannot be extended to total as doing so would imply that K is recursive, which we know is not. However, I am not sure whether this would work within the reduction method or not, as I would apply g(x) only when x $\epsilon$ K.

As for the other two sets: $$ TOT=\{x|\phi_x \text{ is total}\} \\ INF=\{x|dom(\phi_x) \text{is infinite}\} $$

again, I was instructed to use a reduction from $\overline{K}$ to the set, but again I find myself struggling with finding a suitable function for the reduction. Any help with how to better understand the method will be appreciated!

EDIT: I thought about the fact that the literature out there might not be consistent. K is the Halting Problem set, meaning that: $$ K= \{ x | \phi_x(x) \downarrow \} $$

Answer 1

First, a quick comment on extendibility in general. The function $g$ you describe is extendible to a total recursive function, contrary to what you claim - namely, it's extended by the identity function $x\mapsto x$. When we extend a partial recursive function to a total recursive function, we don't need (a priori) to keep track of the original domain, so the fact that $dom(g)$ is complicated in no way directly prevents $g$ from being extendible.

You have to work a bit harder to get a non-extendible function. As a partial hint, note that (fixing some $x$) if we have some $s$ such that we know $$\varphi_x(x)\downarrow\iff\varphi_x(x)[s]\downarrow,$$ then we can tell whether $x\in K$ just by running $\varphi_x(x)$ for $s$-many steps; conversely, for $x\in K$ we can find the stage $s$ at which point $\varphi_x(x)\downarrow$.

---

But let's say we've resolved the problem above, and we have a non-extendible function $h$. Then how can we use this to reduce $\overline{K}$ to $EXT$?

Well, suppose you're given an $x$ and you want to tell whether $x\in \overline{K}$. To do this, you want to build a function $f_x$ which is in $EXT$ iff $x\in\overline{K}$ - that is, iff we never see $\varphi_x(x)$ converge.

The general strategy for doing this sort of thing is to think of $f_x$ in terms of "until" - namely, you want $f_x$ to sound like $$\mbox{"do [blah] until (if ever) $\varphi_x(x)$ converges, after which point do [foo]."}$$ Here [blah] should be some behavior which makes $f_x$ look extendible, and [foo] should be some behavior which makes $f_x$ look non-extendible.

Looking extendible is easy - for example, we can simply require $f_x(y)$ to not be defined until we see $\varphi_x(x)$ converge (the everywhere-undefined function is definitely extendible!). Looking non-extendible is harder, but here's where our $h$ - once we have it - comes in: the $f_x$ we want should be "Look like the always-undefined function until we see $\varphi_x(x)$ converge, at which point behave like $h$." Now you just need to make this precise.