Herbrand consistency and bounded arithmetic

Zofia Adamowicz¹

¹ Institute of Mathematics Polish Academy of Sciences /Sniadeckich 8 00-950 Warszawa, Poland

Fundamenta Mathematicae, Tome 171 (2002) no. 3, pp. 279-292.

Résumé

We prove that the Gödel incompleteness theorem holds for a weak arithmetic $T_m=I \Delta _0+ \Omega _m$, for $m\ge 2$, in the form $T_m\not \vdash {\rm HCons}(T_m)$, where ${\rm HCons}(T_m)$ is an arithmetic formula expressing the consistency of $T_m$ with respect to the Herbrand notion of provability. Moreover, we prove $T_m\not \vdash {\rm HCons}^{I_m}(T_m)$, where ${\rm HCons}^{I_m}$ is ${\rm HCons}$ relativised to the definable cut $I_m$ of $(m-2)$-times iterated logarithms. The proof is model-theoretic. We also prove a certain non-conservation result for $T_m$.

Détail

DOI : 10.4064/fm171-3-7

Keywords: prove del incompleteness theorem holds weak arithmetic delta omega form vdash hcons where hcons arithmetic formula expressing consistency respect herbrand notion provability moreover prove vdash hcons where hcons hcons relativised definable cut m times iterated logarithms proof model theoretic prove certain non conservation result