The idea of interpretability logics arose in Visser [Vis90]. He introduced the logics as extensions of the provability logic GLwith a binary modality. The arithmetic realization of A B in a theory T will be that T plus the realization of B is interpretable in T plus the realization of A. More precisely, there exists a function f on the formulas of the language of T such that T + B C implies T + A f.The interpretability logics were considered (...) in several papers. An arithmetic completeness of the interpretability logic ILM, obtained by adding Montagna ''s axiom to the smallest interpretability logic IL, was proved in Berarducci [Ber90] and Shavrukov [Sha88]. [Vis90] proved that the interpretability logic ILP, an extension of IL, is also complete for another arithmetic interpretation. The completeness with respect to Kripke semantics due to Veltman was, for IL, ILMand ILP, proved in de Jongh and Veltman [JV90]. The fixed point theorem of GLcan be extended to ILand hence ILMand ILP. The unary pendant "T interprets T + A" is much less expressive and was studied in de Rijke [Rij92]. For an overview of interpretability logic, see Visser [Vis97], and Japaridze and de Jongh [JJ98]. (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)

The provability logic of a theory $T$ is the set of modal formulas, which under any arithmetical realization are provable in $T$. We slightly modify this notion by requiring the arithmetical realizations to come from a specified set $\Gamma$. We make an analogous modification for interpretability logics. We first study provability logics with restricted realizations and show that for various natural candidates of $T$ and restriction set $\Gamma$, the result is the logic of linear frames. However, for the theory Primitive (...) Recursive Arithmetic (PRA), we define a fragment that gives rise to a more interesting provability logic by capitalizing on the well-studied relationship between PRA and I$\Sigma_1$. We then study interpretability logics, obtaining upper bounds for IL(PRA), whose characterization remains a major open question in interpretability logic. Again this upper bound is closely related to linear frames. The technique is also applied to yield the nontrivial result that IL(PRA) $\subset$ ILM. (shrink)