How can I prove that primitive recursion "preserves" representability in Peano Arithmetic?

76 Views Asked by At

I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.

By recursive function we understand every function obtained from the successor, zero and identities/projections functions and the methods of composition, minimization and primitive recursion. The definition for representability is that a function $f:\mathbb{N}^m \rightarrow \mathbb{N}$ is represented by a formula $\varphi$ in the language of $\textsf{PA}$ iff for any $k_1,...,k_m \in \mathbb{N}$, the formula

$\forall y[\varphi(\overline{k_1},...,\overline{k_n},y) \leftrightarrow (y=\overline{f(k_1,...,k_n)})]$

is a theorem of PA (i.e., iff $\textsf{PA} \vdash \forall y[\varphi(\overline{k_1},...,\overline{k_n},y) \leftrightarrow (y=\overline{f(k_1,...,k_n)})]$), where $\overline{k_i}$ is the numeral of $k_i$.

Now, my question is: Formally, to prove that every recursive function is representable, we need to prove that there exist formulas that represent the three basic functions (successor, zero and identitites), and that the three methods (composition, minimization and primitive recursion) "preserve" representability -- i.e., that given any functions $f,g$ that are representable in $\textsf{PA}$, then $f \circ g$ is representable, and so are the functions obtained from them by minimization and primitive recursion.

The problem is that I cannot find a reference where the last of these affirmations is proved. All the books I've searched do just the work of proving the cases of composition and minimization, and then they simply say that the case of primitive recursion is too hard (or they, as Boolos does in his Computability and Logic, simply give the formula that represents the proccess -- making the correspondece between this proccess and a sequence of computations --, without proving by the definiton of representability).

At least, finally I found the information, in Richard Zach's Open Introduction to Gödel's Theorems, that, in some way, we can "simulate" primitive recursion just using composition and minimization. So it makes sense that we really can avoid the hard demonstration for the representability of primitive recursion, but I still wanna know why this task is so avoidable (that is, how such a proof goes).