order. Therefore, the set of all primitive recursive functions is countable.
Suppose now that the set of all functions is also countable. We can then write
all functions in some order, say, f 1 ,f 2 ,…. We next construct a function g defined
as
g(i) = f i (i)+ 1, i = 1,2,….
Clearly, g is well defined and is therefore in F, but equally clearly, g differs from
every f i in the diagonal position. This contradiction proves that F cannot be
countable.
Combining these two observations proves that there must be some function
in F that is not primitive recursive.
Actually, this goes even further; not only are there functions that are not
primitive recursive, there are in fact computable functions that are not primitive
recursive.
Theorem 13.2
Let C be the set of all total computable functions from I to I. Then there is some
function in C that is not primitive recursive.
Proof: By the argument of the previous theorem, the set of all primitive
recursive functions is countable. Let us denote the functions in this set as r 1 ,r 2 ,…
and define a function g by
g(i) = r i (i)+1
By construction, the function g differs from every r i and is therefore not
primitive recursive. But clearly g is computable, proving the theorem.
The nonconstructive proof that there are computable functions that are not
primitive recursive is a fairly simple exercise in diagonalization. The actual
construction of an example of such a function is a much more complicated
matter. We will give here one example that looks quite simple; however, the
demonstration that it is not primitive recursive is quite lengthy.