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
    Please verify that I didn’t louse anything up when I added $\LaTeX$ and improved the formatting a bit.2012-04-05
  • 0
    Everything looks great thanks.2012-04-05
  • 0
    What is $ { L } $? Is $Q$ Robinson arithmetic?2012-04-05
  • 2
    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.2012-04-05
  • 0
    @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.2012-04-05
  • 0
    Okay great Brian. I didn't know those two cases were trivial. I have no clue about how to prove minimization, composition, successor, projection (or however else recursive is defined). Honestly I don't even know where to start, but intuition tells me R4 & R5 may be useful in proving minimization.2012-04-05
  • 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$.