The paper begins with a more carefully stated version of ontologically neutral (ON) logic, originally introduced in (Hailperin, 1997). A non-infinitistic semantics which includes a definition of potential infinite validity follows. It is shown, without appeal to the actual infinite, that this notion provides a necessary and sufficient condition for provability in ON logic.

-/- Provability logic is a modal logic that is used to investigate what arithmetical theories can express in a restricted language about their provability predicates. The logic has been inspired by developments in meta-mathematics such as Gödel’s incompleteness theorems of 1931 and Löb’s theorem of 1953. As a modal logic, provability logic has been studied since the early seventies, and has had important applications in the foundations of mathematics. -/- From a philosophical (...) point of view, provability logic is interesting because the concept of provability in a fixed theory of arithmetic has a unique and non-problematic meaning, other than concepts like necessity and knowledge studied in modal and epistemic logic. Furthermore, provability logic provides tools to study the notion of self-reference. (shrink)

We introduce the logics GLP Λ, a generalization of Japaridze’s polymodal provability logic GLP ω where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLP ω yielding among other things a finitary proof of the normal form theorem for the variable-free fragment of GLP Λ and the decidability of GLP Λ for recursive orderings Λ. Further, we give a restricted axiomatization of (...) the variable-free fragment of GLP Λ. (shrink)

Discovering the differences between the various systems of modal logics was one of the advantages of inventing Kripke semantics. One of the most obvious examples is interpreting the necessity of provability in provability logic. According to Boolos in The Logic of Provability, by discovering this logic, we can say that the understanding of new issues in the field of argument was opened. In this paper, with a formal approach and with a descriptive-analytical and comparative (...) method, the axiomatic propositional systems of the GL, Grz, and H, and their possible world semantics based on Kripke semantics are studied, as well as the sequent calculus of GL (in Peano arithmetic) and GLS (in the standard model) were introduced. Finally, the meta-theorems of soundness, consistency, and completeness of the GL were interpreted and proved. (shrink)

We study here extensions of the Artemov's logic of proofs in the language with quantifiers on proof variables. Since the provability operator □ A could be expressed in this language by the formula u[u]A, the corresponding logic naturally extends the well-known modal provability logic GL. Besides, the presence of quantifiers on proofs allows us to study some properties of provability not covered by the propositional logics.In this paper we study the arithmetical complexity of the (...) provability logic with quantifiers on proofs for a given arithmetical theory T and a class of proof predicates.In the last section we define Kripke style semantics for the logics corresponding to the standard Gödel proof predicate and its multiple conclusion version. (shrink)

Provability logics with many modal operators for progressions of theories obtained by iterating their consistency statements are introduced. The corresponding arithmetical completeness theorem is proved.

In this paper are studied the properties of the proofs in PRA of provability logic sentences, i.e. of formulas which are Boolean combinations of formulas of the form PIPRA, where h is the Gödel-number of a sentence in PRA. The main result is a Normal Form Theorem on the proof-trees of provability logic sequents, which states that it is possible to split the proof into an arithmetical part, which contains only atomic formulas and has an essentially (...) intuitionistic character, and into a logical part, which is merely instrumental. Moreover, the induction rules which occur in the arithmetical part are implicit. Some applications of the Normal Form Theorem are shown in order to obtain some syntactical results on the PRA-completeness of modal logic. In particular a completeness theorem for Boolean combinations of modalities is given. (shrink)

We say that two arithmetical formulas A, B have the Σ1-interpolation property if they have an ‘interpolant’ σ, i.e., a Σ1 formula such that the formulas A→σ and σ→B are provable in Peano Arithmetic PA. The Σ1-interpolability predicate is just a formalization of this property in the language of arithmetic.Using a standard idea of Gödel, we can associate with this predicate its provability logic, which is the set of all formulas that express arithmetically valid principles in the modal (...) language with two modal operators, □ for provability in PA and for Σ1-interpolability. In this paper we determine this provability logic .It turns out that this problem appears to be quite similar to the problem of such modal description of relative interpretability, a problem, solved by Berarducci and Shavrukov. However, the present case is sometimes easier. In particular, we prove in this paper the fixed point property and the Craig interpolation property for our modal system ELH. (shrink)

In this paper the system IL for relative interpretability is studied.

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant ‘true’ by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with modalities labeled by natural numbers and ω, where ω corresponds to the full uniform reflection schema, whereas n<ω corresponds to its restriction to arithmetical Πn+1-formulas. (...) This calculus is shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time. (shrink)

Let PLω be the provability logic of IΔ0 + ω1. We prove some containments of the form L ⊆ PLω < Th(C) where L is the provability logic of PA and Th(C) is a suitable class of Kripke frames.

We present some results on algebraic and modal analysis of polynomial distortions of the standard provability predicate in Peano Arithmetic PA, and investigate three provability-like modal systems related to the Gödel–Löb modal system GL. We also present a short review of relational and topological semantics for these systems, and describe the dual category of algebraic models of our main modal system.

The decision problem for provability logic remains PSPACE-complete even if the number of propositional atoms is restricted to one.

Predicate modal formulas with non-modalized quantifiers (call them Q-formulas) are considered as schemata of arithmetical formulas, where is interpreted as the provability predicate of some fixed correct extension T of arithmetic. A method of constructing 1) non-provable in T and 2) false arithmetical examples for Q-formulas by Kripke-like countermodels of certain type is given. Assuming the means of T to be strong enough to solve the (undecidable) problem of derivability in QGL, the Q-fragment of the predicate version of the (...) logic GL, we prove the recursive enumerability of the sets of Q-formulas all arithmetical examples of which are: 1) T-provable, 2) true. In. particular, the first one is shown to be exactly QGL and the second one to be exactly the Q-fragment of the predicate version of Solovay's logic S. (shrink)

For the Heyting Arithmetic HA, $HA^{\text{*}} $ is defined [14, 15] as the theory $\left\{ {A|HA \vdash A^\square } \right\}$, where $A^\square $ is called the box translation of A. We characterize the ${\text{\Sigma }}_1 $-provability logic of $HA^{\text{*}} $ as a modal theory $iH_\sigma ^{\text{*}} $.

Provability logic GLP is well-known to be incomplete w.r.t. Kripke semantics. A natural topological semantics of GLP interprets modalities as derivative operators of a polytopological space. Such spaces are called GLP-spaces whenever they satisfy all the axioms of GLP. We develop some constructions to build nontrivial GLP-spaces and show that GLP is complete w.r.t. the class of all GLP-spaces.

Provability logics are modal or polymodal systems designed for modeling the behavior of Gödel’s provability predicate and its natural extensions. If Λ is any ordinal, the Gödel-Löb calculus GLPΛ contains one modality [λ] for each λ < Λ, representing provability predicates of increasing strength. GLPω has no non-trivial Kripke frames, but it is sound and complete for its topological semantics, as was shown by Icard for the variable-free fragment and more recently by Beklemishev and Gabelaia for the (...) full logic. In this paper we generalize Beklemishev and Gabelaia’s result to GLPΛ for countable Λ. We also introduce provability ambiances, which are topological models where valuations of formulas are restricted. With this we show completeness of GLPΛ for the class of provability ambiances based on Icard polytopologies. (shrink)

Solovay proved (Israel J Math 25(3–4):287–304, 1976) that the propositional provability logic of any ∑2-sound recursively enumerable extension of PA is characterized by the propositional modal logic GL. By contrast, Montagna proved in (Notre Dame J Form Log 25(2):179–189, 1984) that predicate provability logics of Peano arithmetic and Bernays–Gödel set theory are different. Moreover, Artemov proved in (Doklady Akademii Nauk SSSR 290(6):1289–1292, 1986) that the predicate provability logic of a theory essentially depends on the (...) choice of a binumeration of the theory which is used to construct the provability predicate. In this paper, we compare predicate provability logics of I∑ n ’s. For a binumeration α(x) of a recursive theory T, let PL α(T) be the predicate provability logic of T defined by α(x). We prove that for any natural numbers i, j such that 0 < i < j, there exists a ∑1 binumeration α(x) of some recursive axiomatization of I∑ i such that ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsupseteq \bigcap_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ and ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsubseteq \bigcup_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ , where β(x) ranges over all ∑1 binumerations of recursive axiomatizations of I∑ j. (shrink)

In this paper we give a new proof of the characterization of the closed fragment of the provability logic of Heyting's Arithmetic. We also provide a characterization of the closed fragment of the provability logic of Heyting's Arithmetic plus Markov's Principle and Heyting's Arithmetic plus Primitive Recursive Markov's Principle.

A well-known polymodal provability logic inlMMLBox due to Japaridze is complete w.r.t. the arithmetical semantics where modalities correspond to reflection principles of restricted logical complexity in arithmetic. This system plays an important role in some recent applications of provability algebras in proof theory. However, an obstacle in the study of inlMMLBox is that it is incomplete w.r.t. any class of Kripke frames. In this paper we provide a complete Kripke semantics for inlMMLBox . First, we isolate a (...) certain subsystem inlMMLBox of inlMMLBox that is sound and complete w.r.t. a nice class of finite frames. Second, appropriate models for inlMMLBox are defined as the limits of chains of finite expansions of models for inlMMLBox . The techniques involves unions of n -elementary chains and inverse limits of Kripke models. All the results are obtained by purely modal-logical methods formalizable in elementary arithmetic. (shrink)

In this paper we study 1. the frame-theory of certain bimodal provability logics involving the reflection principle and we study2. certain specific bimodal logics with a provability predicate for a subtheory of Peano arithmetic axiomatized by a non-standardly finite number of axioms.

Assuming the existence of suitable large cardinals, we show it is consistent that the Provability logic $\mathbf {GL}$ is complete with respect to the filter sequence of normal measures. This result answers a question of Andreas Blass from 1990 and a related question of Beklemishev and Joosten.

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.

For any ordinal $\Lambda$, we can define a polymodal logic $\mathsf{GLP}_\Lambda$, with a modality $[\xi]$ for each $\xi < \Lambda$. These represent provability predicates of increasing strength. Although $\mathsf{GLP}_\Lambda$ has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted $\mathsf{GLP}^0_\omega$. Later, Icard defined a topological model for $\mathsf{GLP}^0_\omega$ which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for (...) arbitrary $\Lambda$. More generally, for each $\Theta,\Lambda$ we build a Kripke model $\mathfrak I^\Theta_\Lambda$ and a topological model $\mathfrak T^\Theta_\Lambda$, and show that $\mathsf{GLP}^0_\Lambda$ is sound for both of these structures, as well as complete, provided $\Theta$ is large enough. (shrink)

Provability logic is a modal logic for studying properties of provability predicates, and Interpretability logic for studying interpretability between logical theories. Their natural models are GL-models and Veltman models, for which the accessibility relation is well-founded. That’s why the usual counterexample showing the necessity of finite image property in Hennessy-Milner theorem (see [1]) doesn’t exist for them. However, we show that the analogous condition must still hold, by constructing two GL-models with worlds in them that (...) are modally equivalent but not bisimilar, and showing how these GL-models can be converted to Veltman models with the same properties. In the process we develop some useful constructions: games on Veltman models, chains, and general method of transformation from GL-models/frames to Veltman ones. (shrink)

We establish the bi-modal forgetful projection of the Logic of Proofs and Formal Provability GLA. That is to say, we present a normal bi-modal provability logic with modalities □ and whose theorems are precisely those formulas for which the implicit provability assertions represented by the modality can be realized by explicit proof terms.

The provability logic GL was in the field of interest of A.V. Kuznetsov, who had also formulated its intuitionistic analog—the intuitionisticprovability logic—and investigated these two logics and their extensions.In the present paper, different versions of interpolation and of the Bethproperty in normal extensions of the provability logic GL are considered. Itis proved that in a large class of extensions of GL almost all versions of interpolation and of the Beth propertyare equivalent. It follows that in (...) finite slice logics over GL the three versionsCIP, IPD and IPR of the interpolation property are equivalent. Also theyare equivalent to the Beth properties B1, PB1 and PB2. (shrink)

Franco Montagna, a prominent logician and one of the leaders of the Italian school on Mathematical Logic, passed away on February 18, 2015. We survey some of his results and ideas in the two disciplines he greatly contributed along his career: provability logic and many-valued logic.

We consider the well-known provability logic GLP. We prove that the GLP-provability problem for polymodal formulas without variables is PSPACE-complete. For a number n, let L0n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L^{n}_0}$$\end{document} denote the class of all polymodal variable-free formulas without modalities ⟨n⟩,⟨n+1⟩,...\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle n \rangle,\langle n+1\rangle,...}$$\end{document}. We show that, for every number n, the GLP-provability problem for formulas from L0n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L^{n}_0}$$\end{document} is in PTIME. (shrink)

In 1983, Valentini presented a syntactic proof of cut elimination for a sequent calculus GLSV for the provability logic GL where we have added the subscript V for “Valentini”. The sequents in GLSV were built from sets, as opposed to multisets, thus avoiding an explicit contraction rule. From a syntactic point of view, it is more satisfying and formal to explicitly identify the applications of the contraction rule that are ‘hidden’ in these set based proofs of cut elimination. (...) There is often an underly ing assumption that the move to a proof of cut elimination for sequents built from multisets is easy. Recently, however, it has been claimed that Valentini’s arguments to eliminate cut do not terminate when applied to a multiset formulation of GLSV with an explicit rule of contraction. The claim has led to much confusion and various authors have sought new proofs of cut elimination for GL in a multiset setting. Here we refute this claim by placing Valentini’s arguments in a formal setting and proving cut elimination for sequents built from multisets. The formal setting is particularly important for sequents built from multisets, in order to accurately account for the interplay between the weakening and contraction rules. Furthermore, Valentini’s original proof relies on a novel induction parameter called “width” which is computed ‘globally’. It is diffi cult to verify the correctness of his induction argument based on “width”. In our formulation however, verification of the induction argument is straight forward. Finally, the multiset setting also introduces a new complication in the the case of contractions above cut when the cut formula is boxed. We deal with this using a new transformation based on Valentini’s original arguments. Finally, we show that the algorithm purporting to show the non termi nation of Valentini’s arguments is not a faithful representation of the original arguments, but is instead a transformation already known to be insufficient. (shrink)

We consider Hilbert-style non–well-founded derivations in the Gödel-Löb provability logic GL and establish that GL with the obtained derivability relation is globally complete for algebraic and neighbourhood semantics.

This paper concerns modal logics of provability — Gödel-Löb systemGL and Solovay logicS — the smallest and the greatest representation of arithmetical theories in propositional logic respectively. We prove that the decision problem for admissibility of rules (with or without parameters) inGL andS is decidable. Then we get a positive solution to Friedman''s problem forGL andS. We also show that A. V. Kuznetsov''s problem of the existence of finite basis for admissible rules forGL andS has a negative solution. (...) Afterwards we give an algorithm deciding the solvability of logical equations inGL andS and constructing some solutions. (shrink)