With $f_i$ as enumeration of single-place primitive recursive functions, show that $F(n,m) = f_n(m)$ is not primitive recursive via diagonal argument

computabilitylogicrecursion

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:

$(*)\quad$ Given any function $H:\mathbb{N}^2\rightarrow\mathbb{N}$ there is an $h:\mathbb{N}\rightarrow\mathbb{N}$ which is not any of the "rows" of $H$: that is, such that for no $n$ do we have $h\simeq H(n,-)$.

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 $(*)$:

$(\dagger)\quad$ Given any p.r. function $H:\mathbb{N}^2\rightarrow\mathbb{N}$, the function $$g(x)=F(x,x)+17$$ is p.r. and not equal to $G(n,-)$ for any $n$.

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:

If an $F$ as in the OP were p.r., then by plugging in that $F$ for $G$ in $(\dagger)$ we'd get a contradiction. The associated $g$ would not be $F(n,-)$ for any $n$, but would be p.r. since $F$ is - and so would have to be $F(n,-)$ for some $n$.

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.

Related Question