Skip to main navigation Skip to Content
Paper IPM / M / 12493  


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. 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 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir