In computability we define the following basic functions, the zero function, the successor function, and the functions $I_{n,k}(x_1,\ldots,x_n)=x_k$ for $k\leq n$.

Next we define three schemata for generating new functions. We have composition of functions, and we have primitive recursion which states:

If $G\colon\Bbb N^k\to\Bbb N$ and $H\colon\Bbb N^{k+2}\to\Bbb N$, then there exists a unique $F\colon\Bbb N^{k+1}\to\Bbb N$ such that: $$F(\vec x,0)=G(\vec x);\quad F(\vec x,n+1)=H(\vec x,n,F(\vec x,n))$$

And lastly we have the minimization schema, which states that if $F(\vec x,y)$ is a function, then $$G(\vec x)=\min\{y\mid F(\vec x,y)=0\land\forall z<y. F(\vec x,z)\in\Bbb N^+\},$$ is a new function.

The primitive recursive functions are those generated from the basic functions without using minimization, and recursive functions are those generated by using all three schemata.

Now, it is a well-known fact that recursive sets are exactly those which are computable, and those are the sets which are definable by a $\Delta_1$ formula in the language of first-order arithmetic. It is also not hard to show that if a partial function has a graph which is $\Sigma_1$-definable, then the function is recursive, and can be written as a composition and minimization of two primitive recursive functions.

The basic functions are easily functions which are quantifier free, and the composition schema is easily shown to be preserving $\Sigma_1$-definability, and so does minimization. Therefore in order to show that every recursive function is indeed $\Sigma_1$-definable, we only have to show that the recursion schema preserves $\Sigma_1$-definability.

But how do we do that?


I believe you are asking how to show that the primitive recursion scheme, when applied to $\Sigma^0_1$ functions $G$ and $H$, produces another $\Sigma^0_1$ function $F$.

This is because arithmetic is sufficiently expressive to quantify over finite sequences, and $F(x, n) = k$ if and only if there exists a finite sequence $\sigma$ of length $n+1$ such that $\sigma(0) = G(x)$, $\sigma(n) = k$, and for all $i < n$, $\sigma(i+1) = H(x,i,\sigma(i))$. That sentence gives a $\Sigma^0_1$ definition when formalized.

| cite | improve this answer | |
  • $\begingroup$ Yes, you believe correctly. I somehow ended up using a different ad-hoc'ish terminology and halfway through the post I got too lazy to change it. :-) $\endgroup$ – Asaf Karagila Mar 24 '13 at 23:03
  • $\begingroup$ Oh, that's a clever trick. And to think that I had put so much emphasis on encoding finite sequences in the previous exercise, why didn't I think of that? :-) Oh well, it's too late to add this to the homework sheet (and I'd think it's unfair to put something that stumped me for a couple of days). Many thanks! $\endgroup$ – Asaf Karagila Mar 24 '13 at 23:07
  • 1
    $\begingroup$ This also shows why things can go awry when formalize recursive functions inside effective theories, because if the quantifier over "finite" sequences is interpreted in a nonstandard model it may return a sequence of nonstandard length, giving a nonstandard computation history claiming that a computation halts which should not actually halt. This will happen, for example, if we write a recursive function to search for a PA-proof of Con(PA) and then ask various nonstandard models of PA whether the function ever finds a result. $\endgroup$ – Carl Mummert Mar 24 '13 at 23:12
  • $\begingroup$ Yes, I see now why models of $\sf ZF+\lnot Con(ZF)$ (and equally for $\sf PA$) must have non-standard integers. That is a truth I never bothered to look into, and now I know! Thank you again! $\endgroup$ – Asaf Karagila Mar 24 '13 at 23:14

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.