# Recursion schema and the arithmetical hierarchy

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?

-
@Quinn: Thanks. I never heard about that before. – Asaf Karagila Mar 24 '13 at 23:05

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.
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! – Asaf Karagila Mar 24 '13 at 23:14