Let $f_1, f_2, \ldots, f_n, \ldots$ be an enumeration of all the (single place) primitive recursive functions. Let $F$ be the two-place function defined by $F(n,m) = f_n(m)$. Show that $F$ is not primitive recursive.
Hint: You may use that all primitive recursive functions are total. Try a diagonal argument.
What I would start to do is define total primitive recursive functions to encode a pair of natural numbers to a single natural number and the reverse:
\begin{align*}
J &: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \\
G &: \mathbb{N} \to \mathbb{N} \times \mathbb{N} \\
\end{align*}
Seeking a contradiction, consider that $F$ is primitive recursive. It is a two-place function, so $F \circ G$ is a one-place primitive recursive function that appears at some index $k$ in the enumeration of all one-place primitive recursive functions.
\begin{align*}
f_k &= F \circ G \\
F &= f_k \circ J \\
\end{align*}
Then:
\begin{align*}
f_k(J(k, J(k, m))) &= F(k, J(k, m)) = f_k(J(k, m)) = F(k, m) = f_k(m) \\
f_k(J(k, J(k, m))) &= f_k(J(k, m)) = f_k(m) \\
\end{align*}
I'm struggling with forming the diagonal argument. I presume I need to describe some other primitive recursive function that exists at some other index, that can be used to yield a contradiction. But I can't figure out how to do that.
Best Answer
It's a good idea to first recall the standard diagonal argument, which I'll phrase constructively as follows:
The proof is to simply "go down the diagonal and modify:" we set $$h(x)=H(x,x)+17$$ (of course $17$ is arbitrary here).
This suggests a "primitive recursive version" of $(*)$:
Of course the second half of the conclusion is immediate, so all we need to do is show that $g$ is p.r. given that $G$ is p.r. This is a quick exercise in applying the composition rule for p.r. functions.
The point of all this is that $(\dagger)$ is a constructive version of the goal in the OP:
Note that nothing here is special to primitive recursion: any "reasonable" complexity class has a corresponding version of $(*)$. E.g. the polynomial-time-computable total functions are not "polynomial-time-computably countable," and so forth.