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.