In [6] Albert Visser shows that ILP completely axiomatizes all schemata about provability and relative interpretability that are provable in finitely axiomatized theories. In this paper we introduce a system called ILP that completely axiomatizes the arithmetically valid principles of provability in and interpretability over such theories. To prove the arithmetical completeness of ILP we use a suitable kind of tail models; as a byproduct we obtain a somewhat modified proof of Visser's completeness result.

In this paper the modal operator "x is provable in Peano Arithmetic" is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.

In this paper we shall introduce two types of contextual-hierarchical approaches to the strengthened liar problem. These approaches, which we call the ‘standard’ and the ‘alternative’ ch-reconstructions of the strengthened liar problem, differ in their philosophical view regarding the nature of truth and the relation between the truth predicates T r n and T r n+1 of different hierarchy-levels. The basic idea of the standard ch-reconstruction is that the T r n+1-schema should hold for all sentences of \. In contrast, (...) the alternative ch-reconstruction, for which we shall argue in section four, is motivated by the idea that T r n and T r n+1 are coherent in the sense that the same sentences of \ should be true according to T r n and T r n+1. We show that instances of the standard ch-reconstruction can be obtained by iterating Kripke’s strong Kleene jump operator. Furthermore, we will demonstrate how instances of the alternative ch-reconstruction can be obtained by a slight modification of the iterated axiom system KF and of the iterated strong Kleene jump operator. (shrink)

We investigate the bimodal logics sound and complete under the interpretation of modal operators as the provability predicates in certain natural pairs of arithmetical theories . Carlson characterized the provability logic for essentially reflexive extensions of theories, i.e. for pairs similar to . Here we study pairs of theories such that the gap between and is not so wide. In view of some general results concerning the problem of classification of the bimodal provability logics we are particularly interested in such (...) pairs that is axiomatized over by ∏1-sentences only, and, for each n 1, proves the n-times iterated consistency of . A complete axiomatization, along with the appropriate Kripke semantics and decision procedures, is found for the two principal cases: finitely axiomatizable extensions of this sort, like e.g. ), ), etc., and reflexive extensions, like ¦n 1\s}), etc. We show that the first logic, ICP, is the minimal and the second one, RP, is the maximal within the class of the provability logics for such pairs of theories. We also show that there are some provability logics lying strictly between these two. As an application of the results of this paper, in the last section the polymodal provability logics for natural recursive progressions of theories based on iteration of consistency are characterized. We construct a system of ordinal notation , which gives exactly one notation to each constructive ordinal, such that the logic corresponding to any progression along coincides with that along natural Kalmar elementary well-orderings. (shrink)

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

Vardanyan's theorem states that the set of PA-valid principles of Quantified Modal Logic, QML, is complete Π0 2. We generalize this result to a wide class of theories. The crucial step in the generalization is avoiding the use of Tennenbaum's Theorem.

If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.

We investigate the Friedman–Goldfarb–Harrington theorem from two perspectives. Firstly, in the frameworks of classical and modal propositional logics, we study the forms of sentences whose existence is guaranteed by the FGH theorem. Secondly, we prove some variations of the FGH theorem with respect to Rosser provability predicates.

We investigate several consequences of inclusion relations between quantified provability logics. Moreover, we give a necessary and sufficient condition for the inclusion relation between quantified provability logics with respect to \ arithmetical interpretations.

We prove that for each recursively axiomatized consistent extension T of Peano Arithmetic and \, there exists a \ numeration \\) of T such that the provability logic of the provability predicate \\) naturally constructed from \\) is exactly \ \rightarrow \Box p\). This settles Sacchetti’s problem affirmatively.

We prove that for any recursively axiomatized consistent extension T of Peano Arithmetic, there exists a \ provability predicate of T whose provability logic is precisely the modal logic \. For this purpose, we introduce a new bimodal logic \, and prove the Kripke completeness theorem and the uniform arithmetical completeness theorem for \.

In [6] Albert Visser shows that ILP completely axiomatizes all schemata about provability and relative interpretability that are provable in finitely axiomatized theories. In this paper we introduce a system called $\text{ILP}^{\omega}$ that completely axiomatizes the arithmetically valid principles of provability in and interpretability over such theories. To prove the arithmetical completeness of $\text{ILP}^{\omega}$ we use a suitable kind of tail models; as a byproduct we obtain a somewhat modified proof of Visser's completeness result.

To the standard propositional modal system of provability logic constants are added to account for the arithmetical fixed points introduced by Bernardi-Montagna in [5]. With that interpretation in mind, a system LR of modal propositional logic is axiomatized, a modal completeness theorem is established for LR and, after that, a uniform arithmetical completeness theorem with respect to PA is obtained for LR.