Derivability conditions for Robinson arithmetic - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T18:02:20Z http://mathoverflow.net/feeds/question/38874 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38874/derivability-conditions-for-robinson-arithmetic Derivability conditions for Robinson arithmetic Charles Stewart 2010-09-15T21:15:29Z 2010-09-16T04:52:08Z <p>Two pieces of hearsay I have encountered about Robinson's Q:</p> <ol> <li>Q fails to satisfy the Löb derivability conditions;</li> <li>Pudlák criticised the Löb derivability conditions and suggested rival, weaker conditions.</li> </ol> <p>Which leads to three questions, if the above are right:</p> <ol> <li>Which derivability condition(s) does Q not satisfy;</li> <li>What were Pudlák's rival conditions and what was his complaint with the Löb conditions; and</li> <li>Does Q satisfy the rival conditions?</li> </ol> <p>These questions arose from Carl Mummert's answer to a math.sx question of mine, <a href="http://math.stackexchange.com/questions/4648/can-robinsons-q-prove-presburger-arithmetic-consistent" rel="nofollow">Can Robinson's Q prove Presburger arithmetic consistent?</a>.</p> http://mathoverflow.net/questions/38874/derivability-conditions-for-robinson-arithmetic/38924#38924 Answer by Kaveh for Derivability conditions for Robinson arithmetic Kaveh 2010-09-16T04:14:19Z 2010-09-16T04:52:08Z <p>I am not sure if this answers your question, but it was at least too long for a comment.</p> <p>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\$).</p> <p>I am not sure but you might find Pudlak's criticism in the last part of <a href="http://projecteuclid.org/DPubS?verb=Display&amp;version=1.0&amp;service=UI&amp;handle=euclid.pl/1235421927&amp;page=record" rel="nofollow">Hajek and Pudlak</a>, and his alternative condition that you are looking for might be "sequential theory". Also take a look at <a href="http://www.math.cas.cz/~pudlak/consis.ps" rel="nofollow">this article</a> which cites the Bezboruah et al. 1976 paper.</p> <p>(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.) </p>