In 1933 Godel introduced a calculus of provability (also known as modal logic S4) and left open the question of its exact intended semantics. In this paper we give a solution to this problem. We find the logic LP of propositions and proofs and show that Godel's provability calculus is nothing but the forgetful projection of LP. This also achieves Godel's objective of defining intuitionistic propositional logic Int via classical proofs and provides a Brouwer-Heyting-Kolmogorov style provability semantics (...) for Int which resisted formalization since the early 1930s. LP may be regarded as a unified underlying structure for intuitionistic, modal logics, typed combinatory logic and λ-calculus. (shrink)

Provability, Computability and Reflection.

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)

-/- 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)

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 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)

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.

It is shown that all the provably total functions of Basic Arithmetic BA, a theory introduced by Ruitenburg based on Predicate Basic Calculus, are primitive recursive. Along the proof a new kind of primitive recursive realizability to which BA is sound, is introduced. This realizability is similar to Kleene's recursive realizability, except that recursive functions are restricted to primitive recursives.

This book, written by one of the most distinguished of contemporary philosophers of mathematics, is a fully rewritten and updated successor to the author's earlier The Unprovability of Consistency. Its subject is the relation between provability and modal logic, a branch of logic invented by Aristotle but much disparaged by philosophers and virtually ignored by mathematicians. Here it receives its first scientific application since its invention. Modal logic is concerned with the notions of necessity and possibility. What George Boolos (...) does is to show how the concepts, techniques, and methods of modal logic shed brilliant light on the most important logical discovery of the twentieth century: the incompleteness theorems of Kurt Godel and the 'self-referential' sentences constructed in their proof. The book explores the effects of reinterpreting the notions of necessity and possibility to mean provability and consistency. (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)

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.

In this paper, we introduce provability multilattice logic PMLn and multilattice arithmetic MPAn which extends first-order multilattice logic with equality by multilattice versions of Peano axioms. We show that PMLn has the provability interpretation with respect to MPAn and prove the arithmetic completeness theorem for it. We formulate PMLn in the form of a nested sequent calculus and show that cut is admissible in it. We introduce the notion of a provability multilattice and develop algebraic semantics for (...) PMLn on its basis, by the method of Lindenbaum-Tarski algebras we prove the algebraic completeness theorem. We present Kripke semantics for PMLn and establish the Kripke completeness theorem via syntactical and semantic embeddings from PMLn into GL and vice versa. Last but not least, the decidability of PMLn is shown. (shrink)

In this paper, we introduce provability multilattice logic PMLn and multilattice arithmetic MPAn which extends first-order multilattice logic with equality by multilattice versions of Peano axioms. We show that PMLn has the provability interpretation with respect to MPAn and prove the arithmetic completeness theorem for it. We formulate PMLn in the form of a nested sequent calculus and show that cut is admissible in it. We introduce the notion of a provability multilattice and develop algebraic semantics for (...) PMLn on its basis, by the method of Lindenbaum-Tarski algebras we prove the algebraic completeness theorem. We present Kripke semantics for PMLn and establish the Kripke completeness theorem via syntactical and semantic embeddings from PMLn into GL and vice versa. Last but not least, the decidability of PMLn is shown. (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)

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

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)

According to the dialetheist argument from the inconsistency of informal mathematics, the informal version of the Gödelian argument leads us to a true contradiction. On one hand, the dialetheist argues, we can prove that there is a mathematical claim that is neither provable nor refutable in informal mathematics. On the other, the proof of its unprovability is given in informal mathematics and proves that very sentence. We argue that the argument fails, because it relies on the unjustified and unlikely assumption (...) that the informal Gödel sentence is informally provable. (shrink)

In Spescha and Strahm [15], a system of explicit mathematics in the style of Feferman [6] and [7] is introduced, and in Spescha and Strahm [16] the addition of the join principle to is studied. Changing to intuitionistic logic, it could be shown that the provably terminating operations of are the polytime functions on binary words. However, although strongly conjectured, it remained open whether the same holds true for the corresponding theory with classical logic. This note supplements a proof of (...) this conjecture. (shrink)

An insight, Central to platonism, That the objects of pure mathematics exist "in some sense" is probably essential to any adequate account of mathematical truth, Mathematical language, And the objectivity of the mathematical enterprise. Yet a platonistic ontology makes how we can come to know anything about mathematical objects and how we use them a dark mystery. In this paper I propose a framework for reconciling a representation-Relative provability theory of mathematical truth with platonism's valid insights. Besides helping to (...) clarify the ontology of pure mathematics, I think this approach suggests a novel philosophical interpretation of some central results of modern mathematics, Including godel's incompleteness theorems and the independence theorems for the continuum hypothesis. (shrink)

(2) Vol., Classification of Propositional Provability Logics LD Beklemishev Introduction Overview. The idea of an axiomatic approach to the study of ...

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, we investigate Rosser provability predicates whose provability logics are normal modal logics. First, we prove that there exists a Rosser provability predicate whose provability logic is exactly the normal modal logic \. Secondly, we introduce a new normal modal logic \ which is a proper extension of \, and prove that there exists a Rosser provability predicate whose provability logic includes \.

We suggest an algebraic approach to proof-theoretic analysis based on the notion of graded provability algebra, that is, Lindenbaum boolean algebra of a theory enriched by additional operators which allow for the structure to capture proof-theoretic information. We use this method to analyze Peano arithmetic and show how an ordinal notation system up to 0 can be recovered from the corresponding algebra in a canonical way. This method also establishes links between proof-theoretic ordinal analysis and the work which has (...) been done in the last two decades on provability logic and reflection principles. Because of its abstract algebraic nature, we hope that it will also be of interest for non-prooftheorists. (shrink)

We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search (...) problems are “type-2” NP search problems, which take second-order objects as parameters. (shrink)

We sharpen Hájek’s Completeness Theorem for theories extending predicate product logic, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi\forall}$$\end{document}. By relating provability in this system to embedding properties of ordered abelian groups we construct a universal BL-chain L in the sense that a sentence is provable from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi\forall}$$\end{document} if and only if it is an L-tautology. As well we characterize the class of lexicographic sums that have this universality (...) property. (shrink)

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)

We will explicate Cantor’s principle of set existence using the Gödelian intensional notion of absolute provability and John Burgess’ plural logical concept of set formation. From this Cantorian Comprehension principle we will derive a conditional result about the question whether there are any absolutely unprovable mathematical truths. Finally, we will discuss the philosophical significance of the conditional result.

By Solovay’s celebrated completeness result [31] on formal provability we know that the provability logic ${\textbf {GL}}$ describes exactly all provable structural properties for any sound and strong enough arithmetical theory with a decidable axiomatisation. Japaridze generalised this result in [22] by considering a polymodal version ${\mathsf {GLP}}$ of ${\textbf {GL}}$ with modalities $[n]$ for each natural number n referring to ever increasing notions of provability. Modern treatments of ${\mathsf {GLP}}$ tend to interpret the $[n]$ provability (...) notion as “provable in a base theory T together with all true $\Pi ^0_n$ formulas as oracles.” In this paper we generalise this interpretation into the transfinite. In order to do so, a main difficulty to overcome is to generalise the syntactical characterisations of the oracle formulas of complexity $\Pi ^0_n$ to the hyper-arithmetical hierarchy. The paper exploits the fact that provability is $\Sigma ^0_1$ complete and that similar results hold for stronger provability notions. As such, the oracle sentences to define provability at level $\alpha $ will recursively be taken to be consistency statements at lower levels: provability through provability whence the name of the paper. The paper proves soundness and completeness for the proposed interpretation for a wide class of theories, namely for any theory that can formalise the recursion described above and that has some further very natural properties. Some remarks are provided on how the recursion can be formalised into second order arithmetic and on lowering the proof-theoretical strength of these systems of second order arithmetic. (shrink)

We study the decidability of k-provability in \—the relation ‘being provable in \ with at most k steps’—and the decidability of the proof-skeleton problem—the problem of deciding if a given formula has a proof that has a given skeleton. The decidability of k-provability for the usual Hilbert-style formalisation of \ is still an open problem, but it is known that the proof-skeleton problem is undecidable for that theory. Using new methods, we present a characterisation of some numbers k (...) for which k-provability is decidable, and we present a characterisation of some proof-skeletons for which one can decide whether a formula has a proof whose skeleton is the considered one. These characterisations are natural and parameterised by unification algorithms. (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)

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)

The goal of this paper is to explore the significance of Montague’s paradox—that is, any arithmetical theory $T\supseteq Q$ over a language containing a predicate $P$ satisfying $P\rightarrow \varphi $ and $T\vdash \varphi \,\therefore\,T\vdash P$ is inconsistent—as a limitative result pertaining to the notions of formal, informal, and constructive provability, in their respective historical contexts. To this end, the paradox is reconstructed in a quantified extension $\mathcal {QLP}$ of Artemov’s logic of proofs. $\mathcal {QLP}$ contains both explicit modalities $t:\varphi (...) $ and also proof quantifiers $x:\varphi $. In this system, the basis for the rule NEC is decomposed into a number of distinct principles governing how various modes of reasoning about proofs and provability can be internalized within the system itself. A conceptually motivated resolution to the paradox is proposed in the form of an argument for rejecting the unrestricted rule NEC on the basis of its subsumption of an intuitively invalid principle pertaining to the interaction of proof quantifiers and the proof-theorem relation expressed by explicit modalities. (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.

This is a book that every enthusiast for Gödel’s proofs of his incompleteness theorems will want to own. It gives an up-to-date account of connections between systems of modal logic and results on provability in formal systems for arithmetic, analysis, and set theory.

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

BAT is a logic built to capture the inferential behavior of informal provability. Ultimately, the logic is meant to be used in an arithmetical setting. To reach this stage it has to be extended to a first-order version. In this paper we provide such an extension. We do so by constructing non-deterministic three-valued models that interpret quantifiers as some sorts of infinite disjunctions and conjunctions. We also elaborate on the semantical properties of the first-order system and consider a couple (...) of its strengthenings. It turns out that obtaining a sensible strengthening is not straightforward. We prove that most strategies commonly used for strengthening non-deterministic logics fail in our case. Nevertheless, we identify one method of extending the system which does not. (shrink)

We study the relationships between two clusters of axiomatizations of Kripke’s fixed-point models for languages containing a self-applicable truth predicate. The first cluster is represented by what we will call ‘\-like’ theories, originating in recent work by Halbach and Horsten, whose axioms and rules are all valid in fixed-point models; the second by ‘\-like’ theories first introduced by Solomon Feferman, that lose this property but reflect the classicality of the metatheory in which Kripke’s construction is carried out. We show that (...) to any natural system in one cluster—corresponding to natural variations on induction schemata—there is a corresponding system in the other proving the same sentences true, addressing a problem left open by Halbach and Horsten and accomplishing a suitably modified version of the project sketched by Reinhardt aiming at an instrumental reading of classical theories of self-applicable truth. (shrink)

In the paper the joint Logic of Proofs and Provability is presented that incorporates both the modality □ for provability 287–304) and the proof operator tF representing the proof predicate “t is a proof of F” . The obtained system naturally includes both the modal logic of provability GL and Artemov's Logic of Proofs . The presence of the modality □ requires two new operations on proofs that together with operations of allow to realize all the invariant (...) operations on proofs admitting description in the modal propositional language. Logic is proved to be decidable and complete with the intended provability semantics. (shrink)

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)

We consider intuitionistic number theory with recursive infinitary rules . Any primitive recursive binary relation for which transfinite induction schema is provable is in fact well founded. Its ordinal is less than ε 0 if the transfinite induction schema is intuitionistically provable in elementary number theory. These results are provable intuitionistically. In fact, it suffices to consider transfinite induction with respect to one particular number-theoretic property.