0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – hmakholm left over Monica Oct 11 '17 at 12:44
  • $\begingroup$ $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. $\endgroup$ – Sid Caroline Oct 11 '17 at 13:08
  • $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Oct 11 '17 at 13:38
  • $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica Oct 11 '17 at 13:41
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.