There are many reasons to hold that the set of total recursive functions is countable, and among them the two following seem to me to be very powerful and sound:
- The set of total recursive functions is a strict subset of the set of partial recursive functions, which is countable.
- A total recursive function can be calculated by an algorithm. Since algorithms are made of a finite number of symbols, the set of all possible algorithms is countable. Thus, the set of total recursive functions is itself countable.
However, it seems to me that the following argument is proving that the set of total recursive functions is not countable (but I think we have to accept the axiom of choice for countable sets):
1) Suppose that the set of total recursive functions is countable. Then there exist a bijection between this set and the set of natural numbers. Consider such a bijection $h$ from $\mathbb N$ into the set of total recursive functions : through $h$, you can enumerate the set of total recursive functions as following : for all $n$ and all total recursive function $f$, $h(n) = f_n$ (the $n$-th function in the enumeration is thus the image of $n$ by $h$). Here it's worth noting that we do not suppose that this enumeration is recursive because $h$ itself is not total recursive. So we have an enumeration of total recursive functions, and, in spite of the fact that this enumeration is not recursive, for all $n$, $f_n$ is well defined.
2) We build a set of functions $\{k_i\mid i\in\mathbb N\}$, such that for all $i\in\mathbb N$, $k_i(n) = 1$ if $n = i$, and $0$ otherwise. Clearly, all the $k_i$ are recursive.
3) Now consider the following function $g$ defined this way :
$$g(x) = f_n(n) +1 \text { iff } k_n(x) = 1$$
So the function will look like this :
$$g(0) = f_0(0) + 1$$ (since $k_0(0) = 1$, and for all integer $i\neq 0$, $k_i(0) = 0$)
$$g(1) = f_1(1) + 1$$ (same reasoning)
And so on…
This function looks very much like the famous diagonal function used to prove that the set of total recursive functions is not recursively enumerable, except that in this case $g$ is defined by conditions, and all the functions used in the definition (the $f_n$ and the $k_n$, and the successor function) are also recursive: so it looks like (but this is a very unclear point to me, and I'm aware that the whole argument lays on that very point) $g$ is a total recursive function, even though the enumeration is not recursive. But then obviously a contradiction arises, for if $g$ is recursive, then there exists an integer $n$ such that $g = f_n$, and thus, for $g(n)$, since $k_n(n) = 1$, $g(n) = f_n(n) = f_n(n) + 1$
Since our only hypothesis is that the set of total recursive functions is countable, and given the fact that we are lead to a contradiction, we should, therefore, conclude that the set of total recursive functions is not countable.
Now, as you have certainly remarked, the whole problem lies in the question whether $g$ is recursive even though the enumeration of the total recursive functions is not: but again, since it's defined by conditions and using only recursive functions, I have trouble to see exactly why it can't be recursive (maybe a formal answer, showing that a rigorous definition of $g$ uses a recursive enumeration of the set of total recursive functions would do the job
very well).
Thank you for your attention and your help.
Best Answer
Why do you think that $g$ is total recursive? That's a pretty huge leap.
I'm not sure why you think that defining $g$ as:
$$g(x) = f_x(x)+1$$
Is any different than:
$$g(x) = f_n(n)+1\text{ iff } k_n(x)=1$$
Since $k_n(x)=1$ exactly when $x=n$. The $k_i$ seem to be used to obfuscate. They don't make the definition of $g$ any more recursive, because $n\to f_n$ is still not recursive.
The only way to show that a function is recursive is to show a way to compute it. In particular, you can't use $f_x(x)$ to compute it, because the function $h(n,i)=f_n(i)$ is not recursive. Unless you can show a way to compute $g$ without reference to $f_n$ you have not show that $g$ is recursive.
Yes, if we could write infinite computer programs/Turing machines, or whatever, then your code for defining $g(0)=f_0(0)+1$, $g(1)=f_1(1)+1$, etc. would be allowed. But if you could write infinite programs, you could come up with any function $\mathbb N\to\mathbb N$, and your statement that there are only countably many recursive functions would be false.
Computability and recursive functions are about starting with finite definitions of functions. You have to completely tell me how to compute the function with a finite program. You have not done so.
Let's say that you have any function, $H:\mathbb N\to\mathbb N$.
By your reasoning, we could define:
$$G(x) = H(n)\text { iff } k_n(x)=1$$
Because we can define:
$$G(0) = H(0)$$ $$G(1) = H(1)$$ $$...$$
That's patently absurd - this is not a "method" for computing $G$, it's just a statement that $G=H$. If you don't know how to compute $H$, we certainly don't know how to compute $G$. But that's essentially your argument.