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.
Surjective total computable functions are not r.e
computabilitydiagonalization
Related Solutions
Summary: total recursive functions are not recursively enumerable; the proof follows from a typical diagonal argument.
“Recursively enumerable” is a property of a set of integers. “Partial recursive” or “total recursive” or “primitive recursive” are properties of functions from integers to integers. The concepts aren't quite on the same plane. Then there's also the RE complexity class, which is a class of functions from some problem domain to booleans; saying that a decision problem is in RE is equivalent to saying that the language that it recognizes is recursively enumerable, if the language is encoded in in the integers.
It is not possible to encode all functions as integers (by a diagonal argument, the set of all functions from integers to integers is uncountable and therefore you cannot find a distinct integer for every function).
On the other hand, it is possible to encode all partial recursive functions as integers, for example by writing these functions in a programming language and reading the bytes that make up the source code as the digits of some integer in base 256 (there are many programs that implement each function, of course, so pick the one that gives the smallest integer). Note that an encoding must be one-to-one, but need not be surjective. If you take a particular such encoding (any “sensible” one will give equivalent results in the end), then you can consider a class of partial recursive functions (the class of all partial recursive functions, the class of primitive recursive functions, the class of constant functions, etc.) and ask what kind of properties the set of all encodings of such functions have.
The set of encodings of partial recursive functions is recursively enumerable. As above, consider the source code of functions expressed in some idealized programming language. Program sources are easy to enumerate: sort strings by length then in lexicographic order, and skip the ones that are not syntactically well-formed (this is a decidable procedure). You have an enumeration of the partial recursive functions (each function will be reached an infinite number of times in the enumeration since there are infinitely many ways to implement it).
On the other hand, the set of encodings of total recursive functions is not recursively enumerable. As often, the proof is based on a diagonal argument. Let $E(f)$ be the encoding of a function $f$ and $F(x)$ be the preimage of $x$ if it exists (i.e. $E(F(x))=x$). Suppose there is an enumeration $r$ of all encodings of recursive functions, i.e. a recursive function $r : \mathbb{N} \mapsto \mathbb{N}$ such that for any total recursive function $f$, there is an integer $x$ such that $r(x)=E(f)$. Define a function $h : \mathbb{N} \mapsto \mathbb{N}$ by $h(x) = F(r(x))(x) + 1$. Then $h$ is not a total recursive function (otherwise there would be some $x$ such that $h = F(r(x))$). Yet because $r$ is recursive, $h$ is total recursive. The assumption that the set of encodings of total recursive functions is recursively enumerable is thus false.
If you take the class of all primitive recursive functions, then it turns out that the set of encodings is recursively enumerable. In other words, you can list all the primitive recursive functions. The idea is pretty similar to the case of the partial recursive functions above. There is no decision procedure that given a program source, can determine whether it is the source of a primitive recursive function (more generally, there is no such decision procedure for any non-trivial property — this is Rice's theorem). But recall that every function can be implemented in (infinitely) many ways: it's enough to enumerate one implementation of every function. By definition, any primitive recursive function can be expressed with projections, constants, the successor function, composition and primitive recursion. Whether an expression is of this form is easily decidable (it's a context-free grammar plus a check that variable names are used correctly). So there is a way to enumerate a set that contains the source code of every primitive recursive function, and only contains the source code of primitive recursive functions. This provides an enumeration of the set of all encodings of primitive recursive functions.
(The enumeration of primitive recursive functions above lists every function many times, for example the identity function also appears as $x \mapsto x+0$, $x \mapsto S(S(S(x) \times 1)-3))$, etc. Interestingly, it is possible, but a lot more difficult, to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. See The Primitive Recursive Functions are Recursively Enumerable by Stefan Kahrs).
P.S. “We cannot say for some non-primitive non-halting function is it in the set of primitive ones”: true, but that would tend to indicate that the primitive recursive functions are no r.e.; as seen above, they are, because it's enough to find one way of expressing the function that we can tell is primitive recursive. “If total recursive functions are in non-r.e., that means their complement is in r.e.”: no, that's wrong, the non-total-recursive functions are not recursively enumerable either; the halting problem is not semi-decidable either way.
There is a general method to answer this kind of question, which Rogers called the Tarski-Kuratowski computation in his book. You first write down a definition of the set in the arithmetical hierarchy, in which all the leading quantifiers explicitly shown in prenex form and in which the central "matrix" is decidable: $$ e \in \text{Fin} \Leftrightarrow (\exists k)(\forall i)(\forall s) [ \phi_{e,s}(i)\mathord{\downarrow} \Rightarrow i < k]$$ Here as usual $\phi_{e,s}(i)\downarrow$ says that $\phi_e(i)$ halts in no more than $s$ steps, which is a decidable question.
From this, we see that the set Fin is $\Sigma^0_2$. That means you should next try to show the set is $\Sigma^0_2$ hard, at which point you will know the set is $\Sigma^0_2$ complete. In particular, that would mean the set is not r.e. because the r.e. sets are exactly the $\Sigma^0_1$ sets, and a $\Sigma^0_2$ hard set cannot be $\Sigma^0_1$.
In practice, most sets that arise in practice will be complete for the level of the arithmetical hierarchy that the natural prenex form of the set suggests ($\Sigma^0_2$, in this case). That is why this method is worth knowing.
The thing that remains is showing that the set Fin is $\Sigma^0_2$ hard. To do that, suppose you have a $\Sigma^0_2$ formula $\psi(x) \equiv (\exists n)(\forall m)\phi(n,m,x)$. Given $x$, we need to make a program $e = e(x)$ that will be in Fin if and only if $\psi(x)$ holds. That is not too hard to do, using the fact that $\phi(n,m,x)$ is decidable from $n$, $m$, and $x$. I'll leave it to you.
It also helps to know some examples of particular sets at particular levels of the hierarchy:
- The halting set $\{e : \phi_e(0)\mathord{\downarrow}\}$ is $\Sigma^0_1$ complete, and its complement is $\Pi^0_1$ complete.
- Fin is $\Sigma^0_2$ complete. So is the set of programs that compute non-total functions.
- The complement of Fin is the set of programs with infinite domain. This set is $\Pi^0_2$ complete. So is the set of programs that compute total functions.
- The set of programs whose domain is cofinite is $\Sigma^0_3$ complete. Its complement, the set of programs which diverge on an infinite set of inputs, is $\Pi^0_3$ complete.
Once you know these, you can use them to show other sets are at particular levels of the arithmetical hierarchy.
Best Answer
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.