Provability Logic

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)

The research observed, in parallel and comparatively, a surveillance state’s use of communication & cyber networks with satellite applications for power political & realpolitik purposes, in contrast to the outer space security & legit scientific purpose driven cybernetics. The research adopted a psychoanalytic & psychosocial method of observation in the organizational behaviors of the surveillance state, and a theoretical physics, astrochemical, & cosmological feedback method in the contrast group of cybernetics. Military sociology and multilateral movements were adopted in the diagnostic (...) studies & research on cybersecurity, and cross-channeling in communications were detected during the research. The paper addresses several key points of technicalities in security & privacy breach, from personal devices to ontological networks and satellite applications - notably telecommunication service providers & carriers with differentiated spectrum. The paper discusses key moral ethical risks posed in the mal-adaptations in commercial devices that can corrupt democracy in subtle ways but in a mass scale. The research adopted an analytical linguistics approach with linguistic history in unjailing from the artificial intelligence empowered pancomputationalism approach of the heterogenous dictatorial semantic network, and the astronomical & cosmological research in information theory implies that noncomputable processes are the only defense strategy for the new technology-driven pancomputationalism developments. (shrink)

In traditional semantics for classical logic and its extensions, such as modal logic, propositions are interpreted as subsets of a set, as in discrete duality, or as clopen sets of a Stone space, as in topological duality. A point in such a set can be viewed as a "possible world," with the key property of a world being primeness—a world makes a disjunction true only if it makes one of the disjuncts true—which classically implies totality—for each proposition, a world either (...) makes the proposition true or makes its negation true. This chapter surveys a more general approach to logical semantics, known as possibility semantics, which replaces possible worlds with possibly partial "possibilities." In classical possibility semantics, propositions are interpreted as regular open sets of a poset, as in set-theoretic forcing, or as compact regular open sets of an upper Vietoris space, as in the recent theory of "choice-free Stone duality." The elements of these sets, viewed as possibilities, may be partial in the sense of making a disjunction true without settling which disjunct is true. We explain how possibilities may be used in semantics for classical logic and modal logics and generalized to semantics for intuitionistic logics. The goals are to overcome or deepen incompleteness results for traditional semantics, to avoid the nonconstructivity of traditional semantics, and to provide richer structures for the interpretation of new languages. (shrink)

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 study the structure of families of theories in the language of arithmetic extended to allow these families to refer to one another and to themselves. If a theory contains schemata expressing its own truth and expressing a specific Turing index for itself, and contains some other mild axioms, then that theory is untrue. We exhibit some families of true self-referential theories that barely avoid this forbidden pattern.

In "A Problem in Possible-World Semantics," David Kaplan presented a consistent and intelligible modal principle that cannot be validated by any possible world frame (in the terminology of modal logic, any neighborhood frame). However, Kaplan's problem is tempered by the fact that his principle is stated in a language with propositional quantification, so possible world semantics for the basic modal language without propositional quantifiers is not directly affected, and the fact that on careful inspection his principle does not target the (...) world part of possible world semantics—the atomicity of the algebra of propositions—but rather the idea of propositional quantification over a complete Boolean algebra of propositions. By contrast, in this paper we present a simple and intelligible modal principle, without propositional quantifiers, that cannot be validated by any possible world frame precisely because of their assumption of atomicity (i.e., the principle also cannot be validated by any atomic Boolean algebra expansion). It follows from a theorem of David Lewis that our logic is as simple as possible in terms of modal nesting depth (two). We prove the consistency of the logic using a generalization of possible world semantics known as possibility semantics. We also prove the completeness of the logic (and two other relevant logics) with respect to possibility semantics. Finally, we observe that the logic we identify naturally arises in the study of Peano Arithmetic. (shrink)

Turing progressions arise by iteratedly adding consistency statements to a base theory. Different notions of consistency give rise to different Turing progressions. In this paper we present a logic that generates exactly all relations that hold between these different Turing progressions given a particular set of natural consistency notions. Thus, the presented logic is proven to be arithmetically sound and complete for a natural interpretation, named the formalized Turing progressions interpretation.

We investigate relationships between versions of derivability conditions for provability predicates. We show several implications and non-implications between the conditions, and we discuss unprovability of consistency statements induced by derivability conditions. First, we classify already known versions of the second incompleteness theorem, and exhibit some new sets of conditions which are sufficient for unprovability of Hilbert–Bernays’ consistency statement. Secondly, we improve Buchholz’s schematic proof of provable $\Sigma_1$ -completeness. Then among other things, we show that Hilbert–Bernays’ conditions and Löb’s conditions are (...) mutually incomparable. We also show that neither Hilbert–Bernays’ conditions nor Löb’s conditions accomplish Gödel’s original statement of the second incompleteness theorem. (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.

In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem, “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal V}$-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves the open question (...) in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to ${\cal V}$-baos, namely the provability logic $GLB$. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness. (shrink)

This paper propounds a systematic examination of the link between the Knower Paradox and provability interpretations of modal logic. The aim of the paper is threefold: to give a streamlined presentation of the Knower Paradox and related results; to clarify the notion of a syntactical treatment of modalities; finally, to discuss the kind of solution that modal provability logic provides to the Paradox. I discuss the respective strength of different versions of the Knower Paradox, both in the framework of first-order (...) arithmetic and in that of modal logic with fixed point operators. It is shown that the notion of a syntactical treatment of modalities is ambiguous between a self-referential treatment and a metalinguistic treatment of modalities, and that these two notions are independent. I survey and compare the provability interpretations of modality respectively given by Skyrms, B. (1978, The Journal of Philosophy 75: 368–387) Anderson, C.A. (1983, The Journal of Philosophy 80: 338–355) and Solovay, R. (1976, Israel Journal of Mathematics 25: 287–304). I examine how these interpretations enable us to bypass the limitations imposed by the Knower Paradox while preserving the laws of classical logic, each time by appeal to a distinct form of hierarchy. (shrink)

The book studies philosophical and mathematical-logical problems of modal notions. Its starting points are possible worlds semantics and Kripke models, and it also concentrates on proof-theoretic methods.

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)

PA is Peano Arithmetic. Pr(x) is the usual Σ1-formula representing provability in PA. A strong provability predicate is a formula which has the same properties as Pr(·) but is not Σ1. An example: Q is ω-provable if PA + ¬ Q is ω-inconsistent (Boolos [4]). In [5] Dzhaparidze introduced a joint provability logic for iterated ω-provability and obtained its arithmetical completeness. In this paper we prove some further modal properties of Dzhaparidze's logic, e.g., the fixed point property and the Craig (...) interpolation lemma. We also consider other examples of the strong provability predicates and their applications. (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 the system IL for relative interpretability is studied.