Herbrand consistency of some arithmetical theories

Journal of Symbolic Logic 77 (3):807-827 (2012)
  Copy   BIBTEX

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 Mathematical 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∆₀+ Ω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∆₀ + Ω₂ in t itself. In this paper, the above results are generalized for I∆₀ + Ω₁. Also after tailoring the definition of Herbrand consistency for I∆₀ we prove the corresponding theorems for I∆₀. Thus the Herbrand version of Gödel's second incompleteness theorem follows for the theories I∆₀ + Ω₁ and I∆₀

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,075

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The consistency of number theory via herbrand's theorem.T. M. Scanlon - 1973 - Journal of Symbolic Logic 38 (1):29-58.
Saturated models of universal theories.Jeremy Avigad - 2002 - Annals of Pure and Applied Logic 118 (3):219-234.
Arithmetical and specular self-reference.Damjan Bojadžiev - 2004 - Acta Analytica 19 (33):55-63.
Only two letters: The correspondence between herbrand and gödel.Wilfried Sieg - 2005 - Bulletin of Symbolic Logic 11 (2):172-184.

Analytics

Added to PP
2012-11-06

Downloads
37 (#432,128)

6 months
15 (#168,092)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Saeed Salehi
University of Tabriz

Citations of this work

Finitistic Arithmetic and Classical Logic.Mihai Ganea - 2014 - Philosophia Mathematica 22 (2):167-197.

Add more citations

References found in this work

On Herbrand consistency in weak arithmetic.Zofia Adamowicz & Paweł Zbierski - 2001 - Archive for Mathematical Logic 40 (6):399-413.
Passive induction and a solution to a Paris–Wilkie open question.Dan E. Willard - 2007 - Annals of Pure and Applied Logic 146 (2-3):124-149.

Add more references