Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.