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

Salehi, Saeed

J. Symb. Log. 77, No. 3, 807-827 (2012).

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\).

Reviewer: G. E. Mints (Stanford)

MSC:

03F40

Gödel numberings and issues of incompleteness

Keywords:

cut-free provability; Herbrand provability; Herbrand consistency; bounded arithmetics; weak arithmetics; Gödel’s second incompleteness theorem

Citations:

Zbl 0995.03044

References:

[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