4
$\begingroup$

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 math.sx question of mine, Can Robinson's Q prove Presburger arithmetic consistent?.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Commented Sep 15, 2010 at 21:42

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .