We show that a consistent, finitely axiomatized, sequential theory cannot prove its own inconsistency on every definable cut. A corollary is that there are at least three degrees of global interpretability of theories equivalent modulo local interpretability to a consistent, finitely axiomatized, sequential theory U.

In this paper we study local induction w.r.t. Σ1‐formulas over the weak arithmetic. The local induction scheme, which was introduced in, says roughly this: for any virtual class that is progressive, i.e., is closed under zero and successor, and for any non‐empty virtual class that is definable by a Σ1‐formula without parameters, the intersection of and is non‐empty. In other words, we have, for all Σ1‐sentences S, that S implies, whenever is progressive. Since, in the weak context, we have (at (...) least) two definitions of Σ1, we obtain two minimal theories of local induction w.r.t. Σ1‐formulas, which we call Peano Corto and Peano Basso.In the paper we give careful definitions of Peano Corto and Peano Basso. We establish their naturalness both by giving a model theoretic characterization and by providing an equivalent formulation in terms of a sentential reflection scheme.The theories Peano Corto and Peano Basso occupy a salient place among the sequential theories on the boundary between weak and strong theories. They bring together a powerful collection of principles that is locally interpretable in. Moreover, they have an important role as examples of various phenomena in the metamathematics of arithmetical (and, more generally, sequential) theories. We illustrate this by studying their behavior w.r.t. interpretability, model interpretability and local interpretability. In many ways the theories are more like Peano arithmetic or Zermelo Fraenkel set theory, than like finitely axiomatized theories as Elementary Arithmetic, and. On the one hand, Peano Corto and Peano Basso are very weak: they are locally cut‐interpretable in. On the other hand, they behave as if they were strong: they are not contained in any consistent finitely axiomatized arithmetical theory, however strong. Moreover, they extend, the theory of parameter‐free Π1‐induction. (shrink)

We study the arithmetical schema asserting that every eventually decreasing elementary recursive function has a limit. Some other related principles are also formulated. We establish their relationship with restricted parameter-free induction schemata. We also prove that the same principle, formulated as an inference rule, provides an axiomatization of the Σ2-consequences of IΣ1.Using these results we show that ILM is the logic of Π1-conservativity of any reasonable extension of parameter-free Π1-induction schema. This result, however, cannot be much improved: by adapting a (...) theorem of D. Zambella and G. Mints we show that the logic of Π1-conservativity of primitive recursive arithmetic properly extends ILM.In the third part of the paper we give an ordinal classification of -consequences of the standard fragments of Peano arithmetic in terms of reflection principles. This is interesting in view of the general program of ordinal analysis of theories, which in the most standard cases classifies Π-classes of sentences. (shrink)

We characterize the sets of all Π2 and all equation image theorems of IΠ−1 in terms of restricted exponentiation, and use these characterizations to prove that both sets are not deductively equivalent. We also discuss how these results generalize to n > 0. As an application, we prove that a conservation theorem of Beklemishev stating that IΠ−n + 1 is conservative over IΣ−n with respect to equation image sentences cannot be extended to Πn + 2 sentences. © 2011 WILEY-VCH Verlag (...) GmbH & Co. KGaA, Weinheim. (shrink)

We present a comprehensive study of the axiom schemas IΣ - n , BΣ - n (induction and collection schemas for parameter free Σ n formulas) and some closely related schemas.

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.

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in particular $\text{I}\Delta _{0}+\text{EXP}$ . The method is adapted (...) to obtain a similar completeness result for the Rosser logic. (shrink)

A theory T is trustworthy iff, whenever a theory U is interpretable in T, then it is faithfully interpretable. In this paper we give a characterization of trustworthiness. We provide a simple proof of Friedman’s Theorem that finitely axiomatized, sequential, consistent theories are trustworthy. We provide an example of a theory whose schematic predicate logic is complete Π20.

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

I had the pleasure of renewing my acquaintance with Per Lindström at the meeting of the Seventh Scandinavian Logic Symposium, held in Uppsala in August 1996. There at lunch one day, Per said he had long been curious about the development of some of the ideas in my paper [1960] on the arithmetization of metamathematics. In particular, I had used the construction of a non-standard definition !* of the set of axioms of P (Peano Arithmetic) to show that P + (...) {¬ Con!} is interpretable in P, where ! is a standard definition of the axioms of P and Con! expresses the consistency of P via that presentation. Per pointed out that there is a simple “two-line” proof of this interpretability result which does not require the use of such formulas as !*, and he wondered whether I had been aware of that. In fact, his proof had never occurred to me, and if it had at the time, it is possible I would never have been led to the use of non-natural definitions. Per regarded this as a happy accident, since subsequent work by him and others on interpretability made essential use of such definitions. In our conversation, I enlarged a bit on the background to my work on arithmetization, and when I was invited to contribute to this special issue of Theoria dedicated to Lindström, it seemed a natural choice to use the occasion to fill out the story. One caveat, though: the following is drawn largely from memory, not always reliable, supplemented by consultation of the 1960 paper and the 1957 dissertation from which it was drawn. (shrink)

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof be replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic (the so-called Rosser logic of Gauspari-Solovay, 1979) so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in (...) particular I0+EXP. The method is adapted to obtain a similar completeness result for the Rosser logic. (shrink)

In this paper we show how to interpret Robinson’s arithmetic Q and the theory R of Tarski, Mostowski, and Robinson as theories of cardinals in very weak theories of relations over a domain.

Extending previous results from work on the complexity of cut elimination for the sequent calculus LK, we discuss the role of quantifier alternations and develop a measure to describe the complexity of cut elimination in terms of quantifier alternations in cut formulas and contractions on such formulas.