Herbrand consistency of some arithmetical theories. (English) Zbl 1256.03065

Herbrand consistency of a theory \(T\) means that every finite Herbrand conjunction of \(T\) is satisfiable. The author modifies a construction by Z. Adamowicz [Fundam. Math. 171, No. 3, 279–292 (2002; Zbl 0995.03044)] to establish that \(\mathrm{I}\Delta_0+\Omega_1\) does not prove Herbrand consistency of \(\mathrm{I}\Delta_0\).


03F40 Gödel numberings and issues of incompleteness


Zbl 0995.03044
Full Text: DOI arXiv Euclid


[1] Zofia Adamowicz On tableaux consistency in weak theories , preprint # 618, Institute of Mathematics, Polish Academy of Sciences, 34 pp.,2001. · Zbl 0837.03043
[2] —- Herbrand consistency and bounded arithmetic , Fundamenta Mathematicae , vol. 171(2002), no. 3, pp. 279-292. · Zbl 0995.03044
[3] Zofia Adamowicz and Paweł Zbierski On Herbrand consistency in weak arithmetic , Archive for Mathematical Logic , vol. 40(2001), no. 6, pp. 399-413. · Zbl 1030.03043
[4] Zofia Adamowicz and Konrad Zdanowski Lower bounds for the unprovability of Herbrand consistency in weak arithmetics , Fundamenta Mathematicae , vol. 212(2011), no. 3, pp. 191-216. · Zbl 1256.03062
[5] George S. Boolos and Richard C. Jeffrey Computability and Logic , Cambridge University Press,2007.
[6] Samuel R. Buss On Herbrand’s theorem , Proceedings of the International Workshop on Logic and Computational Complexity, October 13-16, 1994 (D. Maurice and R. Leivant, editors), Lecture Notes in Computer Science 960, Springer-Verlag,1995, pp. 195-209.
[7] Petr Hájek and Pavel Pudlák Metamathematics of first-order arithmetic , Springer-Verlag,1998. · Zbl 0889.03053
[8] Leszek A. Kołodziejczyk On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories , Journal of Symbolic Logic, vol. 71(2006), no. 2, pp. 624-638. · Zbl 1099.03050
[9] Jan Krajíček Bounded arithmetic, propositional logic and complexity theory , Cambridge University Press,1995.
[10] Jeff B. Paris and Alex J. Wilkie \(\Delta_0\) sets and induction, Proceedings of Open Days in Model Theory and Set Theory (Guzicki W., Marek W., Plec A., and Rauszer C., editors), Leeds University Press,1981, pp. 237-248.
[11] Pavel Pudlák Cuts, consistency statements and interpretations , Journal of Symbolic Logic, vol. 50(1985), no. 2, pp. 423-441. · Zbl 0569.03024
[12] Saeed Salehi Unprovability of Herbrand consistency in weak arithmetics , Proceedings of the sixth ESSLLI student session, European Summer School for Logic, Language, and Information (Striegnitz K., editor),2001, pp. 265-274.
[13] —- Herbrand consistency in arithmetics with bounded induction , Ph.D. Dissertation, Institute of Mathematics of the Polish Academy of Sciences,2002, 84 pages, available on the net at family http://saeedsalehi.ir/pphd.html.
[14] —- Herbrand consistency of some finite fragments of bounded arithmetical theories , 14 pages, family http://arxiv.org/abs/1110.1848,2011.
[15] —- Separating bounded arithmetical theories by Herbrand consistency , Journal of Logic and Computation , vol. 22(2012), no. 3, pp. 545-560. · Zbl 1252.03136
[16] Dan E. Willard How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson’s arithmetic Q , Journal of Symbolic Logic, vol. 67(2002), no. 1, pp. 465-496. · Zbl 1004.03050
[17] —- Passive induction and a solution to a Paris-Wilkie open question , Annals of Pure and Applied Logic , vol. 146(2007), no. 2-3, pp. 124-149. · Zbl 1115.03083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.