 We have now seen two ways of showing that there exist number theoretic functions which are not primitive recursive—i.e., by observing that while there are only countably many primitive recursive functions there are uncountably many functions of type \(\mathbb{N}^k \rightarrow \mathbb{N}\) (\(k &gt; 0\)) and also by constructing a function such as \(\alpha(x,y) = \alpha_x(y,y)\) which grows faster than any primitive recursive function. A third proof—originally due to Hilbert &amp; Bernays (1934, ch. 7)—is based on the observation that it is possible to enumerate the class \(\mathbf{PR}\) as \(g_0(x),g_1(x),g_2(x), \ldots\)—e.g., by Gödel numbering the sorts of definitions considered at the end of  Section 2.1.1.  If we then consider the modified diagonal function 