$\text{Tot}$ is not computably enumerable

337 Views Asked by At

I'm trying to show that $Tot=\{e: \phi_e \text{ is total}\}$ is not c.e.

Suppose that $Tot$ is c.e. Then its semi-characteristic function is computable. Then the following function $\eta$ is computable:$$\eta(x)\uparrow \text{if } x\in Tot\\ \eta(x)\downarrow \text{ if } x\notin Tot$$

Let $U$ be a universal function. Since $\eta$ is computable, there is $p$ such that $$U(p,x)=\eta(x)$$ for all $x$. $Tot$ can be written as $\{e: U(e,-) \text{ is total}\}$ so setting $x=p$ above we have

$$U(p,p)\uparrow \text{ if } U(p,x)\downarrow\text{ for all } x\\ U(p,p)\downarrow \text{ if } U(p,x_0)\uparrow \text{ for some } x_0$$

There's a contradiction in the first line (but not in the second). Is that enough to conclude that $Tot$ is not c.e.? If not, then how to prove the required result properly?


Actually, now that I've written this proof I started to doubt that $\eta$ is computable. In fact, I don't think that it's computable. How to prove the claim then? (One way is to show that $Tot$ is $\Pi_2$-complete, and hence cannot be $\Sigma_1$, but I wanted a direct proof using some kind of diagonilization argument.)

1

There are 1 best solutions below

0
On

Straightforward proof:

Let $f : \mathbb{N} \to Tot$ be a computable surjection. Then consider the function $g(x) = \phi_{f(x)}(x) + 1$. $g$ is also a computable total function. Therefore, there must exist $n$ such that $\phi_n = g$. Then in particular, there must exist some $x$ such that $\phi_{f(x)} = g$. But in that case, we would have $g(x) = \phi_{f(x)}(x) = \phi_{f(x)}(x) + 1$; contradiction.

Since there is no computable surjection $\mathbb{N} \to Tot$, and since $Tot$ has infinitely many elements, we see that $Tot$ is not computably enumerable.