People have always been interested in numbers, in particular the natural numbers. Of course, we all have an intuitive notion of what these numbers are. In the late 19th century mathematicians, such as Grassmann, Frege and Dedekind, gave definitions for these familiar objects. Since then the development of axiomatic schemes for arithmetic have played a fundamental role in a logical understanding of mathematics. There has been a need for some time for a monograph on the metamathematics of first-order arithmetic. The (...) aim of the book by Hajek and Pudlak is to cover some of the most important results in the study of a first order theory of the natural numbers, called Peano arithmetic and its fragments (subtheories). The field is quite active, but only a small part of the results has been covered in monographs. This book is divided into three parts. In Part A, the authors develop parts of mathematics and logic in various fragments. Part B is devoted to incompleteness. Part C studies systems that have the induction schema restricted to bounded formulas (Bounded Arithmetic). One highlight of this section is the relation of provability to computational complexity. The study of formal systems for arithmetic is a prerequisite for understanding results such as Gödel's theorems. This book is intended for those who want to learn more about such systems and who want to follow current research in the field. The book contains a bibliography of approximately 1000 items. (shrink)

This paper contains a careful derivation of principles of Interpretability Logic valid in extensions of I0+1.

We investigate the theory IΔ 0 + Ω 1 and strengthen [Bu86. Theorem 8.6] to the following: if NP ≠ co-NP. then Σ-completeness for witness comparison formulas is not provable in bounded arithmetic. i.e. $I\delta_0 + \Omega_1 + \nvdash \forall b \forall c (\exists a(\operatorname{Prf}(a.c) \wedge \forall = \leq a \neg \operatorname{Prf} (z.b))\\ \rightarrow \operatorname{Prov} (\ulcorner \exists a(\operatorname{Prf}(a. \bar{c}) \wedge \forall z \leq a \neg \operatorname{Prf}(z.\bar{b})) \urcorner)).$ Next we study a "small reflection principle" in bounded arithmetic. We prove that for (...) all sentences φ $I\Delta_0 + \Omega_1 \vdash \forall x \operatorname{Prov}(\ulcorner \forall y \leq \bar{x} (\operatorname{Prf} (y. \overline{\ulcorner \varphi \urcorner}) \rightarrow \varphi)\urcorner).$ The proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudlak in [Pu86]. Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable Σ-completeness for witness comparison formulas. (shrink)

This paper is concerned with the logical structure of arithmetical theories. We survey results concerning logics and admissible rules of constructive arithmetical theories. We prove a new theorem: the admissible propositional rules of Heyting Arithmetic are the same as the admissible propositional rules of Intuitionistic Propositional Logic. We provide some further insights concerning predicate logical admissible rules for arithmetical theories.

A modal theory Z using the Guaspari witness comparison signs $\leq, is developed. The theory Z is similar to, but weaker than, the theory R of Guaspari and Solovay. Nevertheless, Z proves the independence of the Rosser fixed-point. A Kripke semantics for Z is presented and some arithmetical interpretations of Z are investigated. Then Z is enriched to ZI by adding a new modality sign for interpretability and by axioms expressing some facts about interpretability of theories. Two arithmetical interpretations of (...) ZI are presented. The proofs of the validity of the axioms of ZI in arithmetical interpretations use some strengthening of Solovay's result about interpretability in Godel-Bernays set theory. (shrink)

In this paper I give a characterization of the closed fragment of the provability logic of $I \triangle_0 + \mathrm{EXP}$ with a propositional constant for $\mathrm{EXP}$. In three appendices many details on arithmetization are provided.