# Why is $f_x(x)+1$ not primitive recursive?

So let $f$ be a primitive recursive function with derivation (i.e. a sequence of primitive functions) $f_1, f_2,..., f_k=f$. Let $x\leq k$, then $g(x):=f_x(x)+1$ not primitive recursive, the reason being that $g\neq f_x$ for any $x$.

But how could this be? Surely one can see $g(x):=f_x(x)+1$ is the composition of two primitive recursive functions, $f_x$ and the successor function. So $g$ must also be primitive recursive by closure under composition.

• Hmm... just noticed that you seem to have a finite sequence of functions -- but a primitive recursive function is always total, so what is $g(k+1)$ supposed to be? – hmakholm left over Monica Oct 11 '17 at 12:44
• $g(k+1)=f_{k+1}(k+1)+1$. What is the problem? Oh I see! $k+1>k$, so $g(k+1)$ is undefined. But is that the only problem here? It seems there are more sinister reasons. – Sid Caroline Oct 11 '17 at 13:08
• One further problem -- if we imagine fixing that by defining, for example, that $g(x)=0$ for $x>0$ -- is that just because you have argued that your $g$ differs from each of the $k$ $f_i$s doesn't establish that $g$ is not one of the infinitely many other p.r. functions. – hmakholm left over Monica Oct 11 '17 at 13:38
• If, on the other hand, you fix it by saying that there are now infinitely many $f_i$ which together enumerate all the p.r. functions, then my answer below applies. – hmakholm left over Monica Oct 11 '17 at 13:41

Just because each of your $f_n$s is separately primitive recursive doesn't mean that the function $(n,x)\mapsto f_n(x)$ is primitive recursive.

If that were the case, you could argue that any function whatsoever is primitive recursive: If your desired function is $h$, then for each $n$ let $f_n$ be the constant function that always produces $h(n)$ -- constant functions are always p.r. -- and then $x\mapsto f_x(x)$ would be the same function as your $h$.

While I don't fully understand the motivation behind your question, I think this might be somewhat related.

Let us denote $S$ as a collection of all constant functions (from $\mathbb{N}$ to $\mathbb{N}$). For example when we write the $C_n:\mathbb{N} \rightarrow \mathbb{N}$, we mean the following function: $$C_n(x)=n \qquad for\,\, all \,\, x$$

We can observe the following two properties:

(1) Suppose we have a function $f \in S$. Now define a function $plus:\mathbb{N} \rightarrow \mathbb{N}$ defined by: $$plus(x)=f(x)+1 \qquad for\,\, all \,\, x$$ We have $plus \in S$.

(2) Suppose we have a function $g \in S$. Now define a function $minus:\mathbb{N} \rightarrow \mathbb{N}$ defined by: $$minus(x)=g(x)-1 \qquad for\,\, all \,\, x$$ We have $minus \in S$. The negative sign here obviously means truncated subtraction ($0-1=0$).

Now here is the point I just wanted to make. Suppose we defined two functions $D_1:\mathbb{N} \rightarrow \mathbb{N}$ and $D_2:\mathbb{N} \rightarrow \mathbb{N}$ as: $$D_1(n)=C_n(n)=n \qquad for\,\, all \,\, n$$ $$D_2(n)=C_n(n)+1=n+1 \qquad for\,\, all \,\, n$$ Traditionally when we think of diagnalising through a collection of total functions, a function such as $D_2$ immediately comes to our mind. However, due to the properties (1) and (2) mentioned above we have: $$D_1 \in S \Leftrightarrow D_2 \in S$$ And since we know (due to diagonalisation) that the second proposition above is false (that is, $D_2\notin S$), we can conclude that the first one is false too. So to diagonalise, $D_2$ is not needed after all. So, in this sense, I suppose it could be considered a little peculiar I guess? Note that this observation should be true for any collection of functions that satisfies the properties (1) and (2) above (not just collection of constant functions).