Surjective total computable functions are not r.e

Question

I want to prove by diagonalization that the set of surjective total computable functions from N to N is not recursively enumerable. I know that the result is trivial using Rice's theorem, but I am trying to prove it only by a direct diagonalization argument. However, supposing that we can enumerate the functions of the set, I am unable to construct a proper surjective and total function that cannot belong to the set.

Answer 1

Here's how to use a diagonalization argument to prove something even a bit stronger:

Let $\mathbb N$ be the set of natural numbers (including $0,$ for convenience).

Given any sequence $$\begin{align}&S_0:\mathbb N\to\mathbb N, \\ &S_1:\mathbb N\to\mathbb N, \\ &S_2:\mathbb N\to\mathbb N, \\ &...\end{align}$$ of (total) functions in which every surjective recursive function appears at least once, the function $S: \mathbb N\times\mathbb N \to \mathbb N$ defined by $$S(n, k) = S_n(k)$$ is not recursive.

Assume, aiming at a contradiction, that $S$ is recursive.

Define a function $f: \mathbb N\to\mathbb N$ by setting

$$f(n)=\begin{cases} S(n/2,n)+1, &\text{if }n\text{ is even,} \\ (n-1)/2, &\text{if }n\text{ is odd.}\\ \end{cases}$$

Then $f$ is recursive and surjective, so there exists $e\in\mathbb N$ such that $f = S_e.$

It follows that

$$\begin{align}f(2e) &= S(e,2e)+1 &\text{(by the definition of }f\text{)}\\ &= S_e(2e) + 1 &\text{(by the definition of }S\text{)}\\ &= f(2e) + 1 &\text{(since }f=S_e\text{),}\end{align}$$

which is a contradiction.

Answer 2

We want to show that the total recursive functions cannot be recursively enumerable. In other words, we wish to show that $S = \{n \in \mathbb{N} \mid \{n\}$ is total$\}$ is not recursively enumerable. Here, if $n \in \mathbb{N}$ then $\{n\}$ is the partial recursive function $\mathbb{N} \to \mathbb{N}$ encoded by $n$.

Suppose on the contrary that $S$ is recursively enumerable. Then there exists a surjective total recursive function $g : \mathbb{N} \to S$.

Now define $h(x) = \{g(x)\}(x) + 1$. Then $h$ is a total recursive function. Let $n$ be a code of $h$. Then $n \in S$. Since $g$ is surjective, take some $m$ such that $g(m) = n$.

Then we see that $h$ is a total computable function. Therefore, there exist $n \in S$ such that $\{n\} = h$. Since $n \in S$, there is some $m \in \mathbb{N}$ such that $g(m) = n$.

Then we see that $h(m) = \{g(m)\}(m) + 1$ by the definition of $h$. But we also see that since $h = \{g(m)\}$, we have $h(m) = \{g(m)\}(m)$. Therefore, we have $\{g(m)\}(m) + 1 = \{g(m)\}(m)$, which is a contradiction.