MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Two pieces of hearsay I have encountered about Robinson's Q:

  1. Q fails to satisfy the Löb derivability conditions;
  2. Pudlák criticised the Löb derivability conditions and suggested rival, weaker conditions.

Which leads to three questions, if the above are right:

  1. Which derivability condition(s) does Q not satisfy;
  2. What were Pudlák's rival conditions and what was his complaint with the Löb conditions; and
  3. Does Q satisfy the rival conditions?

These questions arose from Carl Mummert's answer to a question of mine, Can Robinson's Q prove Presburger arithmetic consistent?.

share|cite|improve this question
I can take blame for passing along part (1) of the hearsay. When I went back to look for where I had seen it, I found published claims that Q is "too weak" to prove the derivability conditions, but not an explicit example nor a reference. Perhaps those authors were only referring to the fact that the usual proofs of the derivability conditions don't go through in Q, and I read too much into their statements. So I'm also interested to learn whether there is a published counterexample to the provability of the derivability conditions in Q. – Carl Mummert Sep 15 '10 at 21:42

I am not sure if this answers your question, but it was at least too long for a comment.

First, note than one can interpret Sam Buss's bounded arithmetic theories like $S^1_2$ in $Q$, so it is not as weak as it seems at first sight in expressing and proving theorems. One can use a reasonable formula to exclude those non-standard numbers which are too pathological and prove consistency of $L$ (if $S^1_2$ proves consistency of $L$).

I am not sure but you might find Pudlak's criticism in the last part of Hajek and Pudlak, and his alternative condition that you are looking for might be "sequential theory". Also take a look at this article which cites the Bezboruah et al. 1976 paper.

(By the way, Bezboruah et al. (1976) seems to be a decade before Nelson's Predicative Arithmetic (1986) which shows that one can interpret $I\Delta_0$ in 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.