# Proving Recursive Functions are Representable in R

I am trying to prove that all recursive functions are representable in the theory $R$ whose language is $L$ and whose theorems are the consequences in $L$ of the following infinitely many sentences:

1. $\mathbf{i}\ne\mathbf{j}$ for all $i,j$ such that $i\ne j$
2. $\mathbf{i}+\mathbf{j}=\mathbf{k}$ for all $i,j,k$ such that $i+j=k$
3. $\mathbf{i}\cdot\mathbf{j}=\mathbf{k}$ for all $i,j,k$ such that $i\cdot j=k$
4. $\forall x(x<\mathbf{i}\to x=\mathbf{0}\lor\dots\lor x=\mathbf{i-1})$ for all $i$
5. $\forall x(x<\mathbf{i}\lor x=\mathbf{i}\lor\mathbf{i}<x)$ for all $i$

I am having trouble proving minimization, composition, successor, projection, addition and multiplication.

I attempted to prove the theorems using Boolos' model of proof from $Q$ but I quickly got stuck, since the proof of representability using $Q$ in Boolos uses axioms $R$ doesn't have. The notes I am using can be found here starting on page 94.

-
Please verify that I didn’t louse anything up when I added $\LaTeX$ and improved the formatting a bit. –  Brian M. Scott Apr 5 '12 at 1:28
Everything looks great thanks. –  Quaternary Apr 5 '12 at 1:34
What is ${ L }$? Is $Q$ Robinson arithmetic? –  Henning Makholm Apr 5 '12 at 1:39
For starters, addition barely requires proof: it’s given you by Axiom R2, which already tells you that $R\vdash\mathbf{i}+\mathbf{j}=\mathbf{k}$ whenever $i+j=k$. The same goes for multiplication: you get it for free from R3. –  Brian M. Scott Apr 5 '12 at 1:39
@Henning: Yes, $Q$ is Robinson’s arithmetic, though I had to track back to p. 85 of the notes to check. It doesn’t matter, though, since the problem is entirely about $R$, whose axioms Quaternary has given. –  Brian M. Scott Apr 5 '12 at 1:45

The key here is that the set of axioms are complete for bounded sentences in the language $\{0,1,+,\cdot,\leq \}$ (exercise). So just forget about proving using the axioms, as long as you find a bounded formula that correctly represents the required function in the standard model, the provability will follow and you will get (weak) representability. In fact you can use exactly the same ones used for $Q$.