“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 12493
School of Mathematics
  Title:   Herbrand consistency of some arithmetical theories
  Author(s):  S. Salehi
  Status:   Published
  Journal: J. Symbolic Logic
  Vol.:  77
  Year:  2012
  Pages:   807-827
  Supported by:  IPM
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. In this paper, the above results are generalized for IΔ0+Ω1. Also after tailoring the definition of Herbrand consistency for IΔ0 we prove the corresponding theorems for IΔ0. Thus the Herbrand version of Gödel's second incompleteness theorem follows for the theories IΔ0+Ω1 and IΔ0.

Download TeX format
back to top
scroll left or right