Herbrand consistency of some finite fragments of bounded arithmetical theories

DOI10.1007/S00153-012-0318-3MaRDI QIDQ2377353zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Saeed Salehi

Publication date 28 June 2013

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1848

zbMATH Keywords

bounded arithmeticGödel's second incompleteness theoremHerbrand consistency

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40)

Abstract: We formalize the notion of Herbrand Consistency in an appropriate way for bounded arithmetics, and show the existence of a finite fragment of $mIDelt{a}_0$ whose Herbrand Consistency is not provable in the thoery $mIDelt{a}_0$. We also show the existence of an $mIDelt{a}_0-$derivable $P{i}_1-$sentence such that $mIDelt{a}_0$ cannot prove its Herbrand Consistency.

Review text

A theory \(T\) is Herbrand consistent if every finite set of instances of its Skolemized form is propositionally satisfiable. The author presents a formalization of Herbrand consistency suitable for bounded arithmetic and exhibits a finite fragment of \(I\Delta_0\) whose Herbrand consistency is not provable in \(I\Delta_0\). This improves a previous result of the author that \(I\Delta_0\) does not prove a form of its own Herbrand consistency [the author, J. Symb. Log. 77, No. 3, 807--827 (2012; Zbl 1256.03065)] building on related results by \textit{Z. Adamowicz} [Fundam. Math. 171, No. 3, 279--292 (2002; Zbl 0995.03044)], \textit{D. E. Willard} [J. Symb. Log. 67, No. 1, 465--496 (2002; Zbl 1004.03050)], and \textit{L. A. Kołodziejczyk} [J. Symb. Log. 71, No. 2, 624--638 (2006; Zbl 1099.03050)].

Recommendations

• Separating bounded arithmetical theories by Herbrand consistency
• Herbrand consistency of some arithmetical theories
• Herbrand consistency and bounded arithmetic
• Lower and upper bounds for the provability of Herbrand consistency in weak arithmetics
• On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories

Cites work

• Herbrand consistency and bounded arithmetic
• Herbrand consistency of some arithmetical theories
• How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q
• scientific article; zbMATH DE number 1144041 (Why is no real title available?)
• Lower and upper bounds for the provability of Herbrand consistency in weak arithmetics
• On Herbrand consistency in weak arithmetic
• On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories
• Passive induction and a solution to a Paris-Wilkie open question
• Separating bounded arithmetical theories by Herbrand consistency

Cited in

(11)

• Remarks on Herbrand normal forms and Herbrand realizations
• Herbrand consistency and bounded arithmetic
• Separating bounded arithmetical theories by Herbrand consistency
• Herbrand consistency of some arithmetical theories
• Lower and upper bounds for the provability of Herbrand consistency in weak arithmetics
• scientific article; zbMATH DE number 440482 (Why is no real title available?)
• Herbrandizing search problems in Bounded Arithmetic
• scientific article; zbMATH DE number 4145897 (Why is no real title available?)
• Consistency proof of a fragment of PV with substitution in bounded arithmetic
• On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories
• On Herbrand consistency in weak arithmetic

This page was built for publication: Herbrand consistency of some finite fragments of bounded arithmetical theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2377353)