IM PAN
INSTITUTE OF MATHEMATICS · POLISH ACADEMY OF SCIENCES
FUNDAMENTA
MATHEMATICAE
ISSN: 0016-2736(p) 1730-6329(e)
 

Herbrand consistency and bounded arithmetic
Zofia Adamowicz1
Fund. Math. 171 (2002), 279-292
doi:10.4064/fm171-3-7

Abstract: 
We prove that the G{\accent "7F o}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 {\fam 0\ninerm HCons}(T_m)$, where ${\fam 0\ninerm 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 {\fam 0\ninerm HCons}^{I_m}(T_m)$, where ${\fam 0\ninerm HCons}^{I_m}$ is ${\fam 0\ninerm 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$.\vadjust {\vskip -1pt}


MSC (2000): Primary 03F30.
Retrieve article in PDF (155.14 Kb)
  1. Institute of Mathematics
    Polish Academy of Sciences
    Ĺšniadeckich 8
    00-950 Warszawa, Poland