Herbrand Consistency of Some Arithmetical Theories

Abstract

Gödel's second incompleteness theorem is proved for Herbrand consistency of some arithmetical theories with bounded induction, by using a technique of logarithmic shrinking the witnesses of bounded formulas, due to Z. Adamowicz [Herbrand consistency and bounded arithmetic, \textit{Fundamenta Mathematicae} 171 (2002) 279--292]. In that paper, it was shown that one cannot always shrink the witness of a bounded formula logarithmically, but in the presence of Herbrand consistency, for theories $\mathrm{I}{\mathrm{\Delta }}_0+{\mathrm{\Omega }}_{\mathrm{m}}$ with $m⩾2$, any witness for any bounded formula can be shortened logarithmically. This immediately implies the unprovability of Herbrand consistency of a theory $T\supseteq \mathrm{I}{\mathrm{\Delta }}_0+{\mathrm{\Omega }}_2$ in $T$ itself. In this paper, the above results are generalized for $\mathrm{I}{\mathrm{\Delta }}_0+{\mathrm{\Omega }}_1$. Also after tailoring the definition of Herbrand consistency for $\mathrm{I}{\mathrm{\Delta }}_0$ we prove the corresponding theorems for $\mathrm{I}{\mathrm{\Delta }}_0$. Thus the Herbrand version of Gödel's second incompleteness theorem follows for the theories $\mathrm{I}{\mathrm{\Delta }}_0+{\mathrm{\Omega }}_1$ and $\mathrm{I}{\mathrm{\Delta }}_0$.

References in corpus (2)

• Separating Bounded Arithmetics by Herbrand Consistency
• Herbrand Consistency of Some Finite Fragments of Bounded Arithmetical Theories

Cited by in corpus (2)

• Separating Bounded Arithmetics by Herbrand Consistency
• Herbrand Consistency of Some Finite Fragments of Bounded Arithmetical Theories