Herbrand consistency of some arithmetical theories

Publisher: Cambridge University Press

E-ISSN: 1943-5886|77|3|807-827

ISSN: 0022-4812

Source: The Journal of Symbolic Logic, Vol.77, Iss.3, 2012-09, pp. : 807-827

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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, Fundamenta Mathematicae , vol. 171 (2002), pp. 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 IΔ0 + Ω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 ⊇ IΔ0 + Ω2 in T itself.