2
$\begingroup$

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

  • 0
    The hard part, surely, is proving that primitive recursion is representable in this language...?2012-05-07

1 Answers 1

2

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