We consider structural completeness in modal logics. The main result is the necessary and sufficient condition for modal logics over K4 to be hereditarily structurally complete: a modal logic λ is hereditarily structurally complete $\operatorname{iff} \lambda$ is not included in any logic from the list of twenty special tabular logics. Hence there are exactly twenty maximal structurally incomplete modal logics above K4 and they are all tabular.

Halldén completeness closely resembles the relevance property. To prove Halldén completeness in terms of Kripke-style semantics, the van Benthem–Humberstone theorem is often used. In relevant modal logics, the Halldén completeness of Meyer–Fuhrmann logics has been obtained using the van Benthem–Humberstone theorem. However, there remain a number of Halldén-incomplete relevant modal logics. This paper discusses the Halldén completeness of a wider class of relevant modal logics, namely, those with some Sahlqvist axioms.

Well-known results due to David Makinson show that there are exactly two Post complete normal modal logics, that in both of them, the modal operator is truth-functional, and that every consistent normal modal logic can be extended to at least one of them. Lloyd Humberstone has recently shown that a natural analog of this result in congruential modal logics fails, by showing that not every congruential modal logic can be extended to one in which the (...) modal operator is truth-functional. As Humberstone notes, the issue of Post completeness in congruential modal logics is not well understood. The present article shows that in contrast to normal modal logics, the extent of the property of Post completeness among congruential modal logics depends on the background set of logics. Some basic results on the corresponding properties of Post completeness are established, in particular that although a congruential modal logic is Post complete among all modal logics if and only if its modality is truth-functional, there are continuum many modal logics Post complete among congruential modal logics. (shrink)

A variety of modal logics based on the relevant logic R are presented. Models are given for each of these logics and completeness is shown. It is also shown that each of these logics admits Ackermann's rule γ and as a corollary of this it is proved that each logic is a conservative extension of its counterpart based on classical logic, hence we call them “classically complete”. MSC: 03B45, 03B46.

In previous works, we presented a modification of the usual possible world semantics by introducing an independent temporal structure in each world and using accessibility functions to represent the relation among them. Different properties ofthe accessibility functions have been considered and axiomatic systems which define these properties have been given. Only a few ofthese systems have been proved tobe complete. The aim ofthis paper is to make a progress in the study ofcompleteness for functional systems. For this end, we use (...) indexes as names for temporal flows and give new proofs of completeness. Specifically, we focus our attention on the system which defines injectivity, because the system which defines this property without using indexes was proved to be incomplete in previous works. The only system considered which remains incomplete is the one which defines surjectivity, even ifwe consider a sequence ofnatural extensions ofthe previous one. (shrink)

The addition of "actually" operators to modal languages allows us to capture important inferential behaviours which cannot be adequately captured in logics formulated in simpler languages. Previous work on modal logics containing "actually" operators has concentrated entirely upon extensions of KT5 and has employed a particular modeltheoretic treatment of them. This paper proves completeness and decidability results for a range of normal and nonnormal but quasi-normal propositional modal logics containing "actually" operators, the weakest of which are conservative (...) extensions of K, using a novel generalisation of the standard semantics. (shrink)

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 \.

I present here a modal extension of T called KTLM which is, by several measures, the simplest modal extension of T yet presented. Its axiom uses only one sentence letter and has a modal depth of 2. Furthermore, KTLM can be realized as the logical union of two logics KM and KTL which each have the finite model property (f.m.p.), and so themselves are complete. Each of these two component logics has independent interest as well.

Versions and extensions of intuitionistic and modal logic involving biHeyting and bimodal operators, the axiom of constant domains and Barcan's formula, are formulated as structured categories. Representation theorems for the resulting concepts are proved. Essentially stronger versions, requiring new methods of proof, of known completeness theorems are consequences. A new type of completeness result, with a topos theoretic character, is given for theories satisfying a condition considered by Lawvere . The completeness theorems are used to conclude results asserting that (...) certain logics are conservatively interpretable in others. (shrink)

Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the (...) same consequence relations for a given spi-logic. (shrink)

ABSTRACT We characterize those binary ramified frames for which propositional modal logic is as expressive as the corresponding first-order logic.

This paper presents a recent formalization of a Henkin-style completeness proof for the propositional modal logic S5 using the Lean theorem prover. The proof formalized is close to that of Hughes and Cresswell, but the system, based on a different choice of axioms, is better described as a Mendelson system augmented with axiom schemes for K, T, S4, and B, and the necessitation rule as a rule of inference. The language has the false and implication as the only primitive (...) logical connectives and necessity as the only primitive modal operator. The full source code is available online and has been typechecked with Lean 3.4.2. (shrink)

We show in ZFC that the existence of completely separable maximal almost disjoint families of subsets of $\omega $ implies that the modal logic $\mathbf {S4.1.2}$ is complete with respect to the Čech–Stone compactification of the natural numbers, the space $\beta \omega $. In the same fashion we prove that the modal logic $\mathbf {S4}$ is complete with respect to the space $\omega ^*=\beta \omega \setminus \omega $. This improves the results of G. Bezhanishvili and J. Harding in (...) [4], where the authors prove these theorems under stronger assumptions. Our proof is also somewhat simpler. (shrink)

We show that there are denumerably many Post-complete normal modal logics in the language which includes an additional propositional constant. This contrasts with the case when there is no such constant present, for which it is well known that there are only two such logics.

Quasi-Boolean modal algebras are quasi-Boolean algebras with a modal operator satisfying the interaction axiom. Sequential quasi-Boolean modal logics and the relational semantics are introduced. Kripke-completeness for some quasi-Boolean modal logics is shown by the canonical model method. We show that every descriptive persistent quasi-Boolean modal logic is canonical. The finite model property of some quasi-Boolean modal logics is proved. A cut-free Gentzen sequent calculus for the minimal quasi-Boolean logic is developed and we show that (...) it has the Craig interpolation property. (shrink)

We initiate the study of computable model theory of modal logic, by proving effective completeness theorems for a variety of first-order modal logics. We formulate a natural definition of a decidable Kripke model, and show how to construct such a decidable Kripke model of a given decidable theory. Our construction is inspired by the effective Henkin construction for classical logic. The Henkin construction, however, depends in an essential way on the Deduction Theorem. In its usual form the Deduction (...) Theorem fails for modal logic. In our construction, the Deduction Theorem is replaced by a result about objects called finite Kripke diagrams. We argue that this result can be viewed as an analogue of the Deduction Theorem for modal logic. (shrink)

Gives the first published adaptation of the Lindenbaum/Henkin method of maximal consistent sets for establishing the completeness of modal propositional logics with respect to the relational models of Kripke.

We prove strong completeness results for some modal logics with the universal modality, with respect to their topological semantics over 0-dimensional dense-in-themselves metric spaces. We also use failure of compactness to show that, for some languages and spaces, no standard modal deductive system is strongly complete.

Quasi-Boolean modal algebras are quasi-Boolean algebras with a modal operator satisfying the interaction axiom. Sequential quasi-Boolean modal logics and the relational semantics are introduced. Kripke-completeness for some quasi-Boolean modal logics is shown by the canonical model method. We show that every descriptive persistent quasi-Boolean modal logic is canonical. The finite model property of some quasi-Boolean modal logics is proved. A cut-free Gentzen sequent calculus for the minimal quasi-Boolean logic is developed and we show that (...) it has the Craig interpolation property. (shrink)

We investigate a recent proposal for modal hypersequent calculi. The interpretation of relational hypersequents incorporates an accessibility relation along the hypersequent. These systems give the same interpretation of hypersequents as Lellman's linear nested sequents, but were developed independently by Restall for S5 and extended to other normal modal logics by Parisi. The resulting systems obey Došen's principle: the modal rules are the same across different modal logics. Different modal systems only differ in the presence or (...) absence of external structural rules. With the exception of S5, the systems are modular in the sense that different structural rules capture different properties of the accessibility relation. We provide the first direct semantical cut-free completeness proofs for K, T, and D, and show how this method fails in the case of B and S4. (shrink)

We propose a new approach to positive modal logics, hereby called anodic modal logics. Our treatment is completely positive since the language has neither negation nor any falsum or minimal particle. The elimination of the minimal particle of the language requires introducing the new concept of factual sets and factual deductions which permit us to talk about deductions in the actual world. We start from a positive fragment of the standard system K, denoted by K⊃, ∧, ◊, which (...) is a bimodal system with □ and ◊ as primitive. This system is then extended to a class of fragments of the Lemmon and Scott systems (cf. (Lemmon et al., 1977)), denoted by K⊃, ∧, ◊ + Gk;l;m;n + Gm;n;k;l. It is shown that such classes of systems are characterized with respect to the usual Kripke-style semantics. The proof is by way of a Henkin-style construction, with “possible worlds” being taken to be prime theories as introduced in the modal context by J. M. Dunn in (Dunn, 1995). We also obtain a surprising limiting result showing that the incompleteness phenomenon in modal logic is independent of negation. (shrink)

We show in ZFC that the existence of completely separable maximal almost disjoint families of subsets of $\omega $ implies that the modal logic $\mathbf {S4.1.2}$ is complete with respect to the Čech–Stone compactification of the natural numbers, the space $\beta \omega $. In the same fashion we prove that the modal logic $\mathbf {S4}$ is complete with respect to the space $\omega ^*=\beta \omega \setminus \omega $. This improves the results of G. Bezhanishvili and J. Harding in (...) [4], where the authors prove these theorems under stronger assumptions. Our proof is also somewhat simpler. (shrink)

Halldén complete modal logics are defined semantically. They have a nice characterization as they are determined by homogeneous Kripke frames.

ABSTRACT We consider the question of the complete axiomatization of a relative modal logic with composition and intersection.

Ken Pledger devised a one-sorted approach to the incidence relation of plane geometries, using structures that also support models of propositional modal logic. He introduced a modal system 12g that is valid in one-sorted projective planes, proved that it has finitely many non-equivalent modalities, and identified all possible modality patterns of its extensions. One of these extensions 8f is valid in elliptic planes. These results were presented in his 1980 doctoral dissertation, which is reprinted in this issue of (...) the Australasian Journal of Logic. Here we show that 12g and 8f are strongly complete for validity in their intended one-sorted geometrical interpretations, and have the finite model property. The proofs apply standard technology of modal logic together with a step-by-step procedure introduced by Yde Venema for constructing two-sorted projective planes. (shrink)

The paper generalises Goldblatt's completeness proof for Lemmon–Scott formulas to various modal propositional logics without classical negation and without ex falso, up to positive modal logic, where conjunction and disjunction, andwhere necessity and possibility are respectively independent.Further the paper proves definability theorems for Lemmon–Scottformulas, which hold even in modal propositional languages without negation and without falsum. Both, the completeness theorem and the definability theoremmake use only of special constructions of relations,like relation products. No second order logic, no (...) general frames are involved. (shrink)

We study a modal extension of the Continuous First-Order Logic of Ben Yaacov and Pedersen :168–190, 2010). We provide a set of axioms for such an extension. Deduction rules are just Modus Ponens and Necessitation. We prove that our system is sound with respect to a Kripke semantics and, building on Ben Yaacov and Pedersen, that it satisfies a number of properties similar to those of first-order predicate logic. Then, by means of a canonical model construction, we get that (...) every consistent set of formulas is satisfiable. From the latter result we derive an Approximated Strong Completeness Theorem, in the vein of Continuous Logic, and a Compactness Theorem. (shrink)

This paper expands upon the work by Wang (Proceedings of TARK, pp. 493–512, 2017) who proposes a new framework based on quantifier-free predicate language extended by a new bundled modality $\exists x\Box$ and axiomatizes the logic over S5 frames. This paper first gives complete axiomatizations of the logics over K, D, T, 4, S4 frames with increasing domains and constant domains, respectively. The systems w.r.t. constant domains feature infinitely many additional rules defined inductively than systems w.r.t. increasing domains. In (...) the second part of the paper, we show that these rules are admissible in the systems without them by providing a general strategy for proving completeness theorems for the logics without these rules over constant domain models (also increasing domain models). (shrink)

Unifiability of terms (and formulas) and structural completeness in the variety of relation algebras RA and in the products of modal logic S5 is investigated. Nonunifiable terms (formulas) which are satisfiable in varieties (in logics) are exhibited. Consequently, RA and products of S5 as well as representable diagonal-free n-dimensional cylindric algebras, RDfn, are almost structurally complete but not structurally complete. In case of S5n a basis for admissible rules and the form of all passive rules are provided.

Fibring is defined as a mechanism for combining logics with a first-order base, at both the semantic and deductive levels. A completeness theorem is established for a wide class of such logics, using a variation of the Henkin method that takes advantage of the presence of equality and inequality in the logic. As a corollary, completeness is shown to be preserved when fibring logics in that class. A modal first-order logic is obtained as a fibring where neither the Barcan (...) formula nor its converse hold. (shrink)

Apostoli and Brown have shown that the class of formulae valid with respect to the class of -ary relational frames is completely axiomatized by Kn: an n-place aggregative system which adjoins [RM], [RN], and a complete axiomatization of propositional logic, with [Kn]:□α1 ∧...∧□αn+1 → □2/ is the disjunction of all pairwise conjunctions αi∧αj )).Their proof exploits the chromatic indices of n-uncolourable hypergraphs, or n-traces. Here, we use the notion of the χ-product of a family of sets to formulate an alternative (...) definition of an n-trace, which in turn enables a new and simpler completeness proof. (shrink)

The paper expands upon the work by Wang [4], who proposes a new framework based on quantifier-free predicate language extended by a new modality ∃x□\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exists x\Box$$\end{document} and axiomatizes the logic over S5 frames. This paper gives the logics over K, D, T, 4, S4 frames with increasing and constant domains. And we provide a general strategy for proving completeness theorems for logics w.r.t. the increasing domain and logics w.r.t. the constant (...) domain respectively. (shrink)

A general strategy for proving completeness theorems for quantified modal logics is provided. Starting from free quantified modal logic K, with or without identity, extensions obtained either by adding the principle of universal instantiation or the converse of the Barcan formula or the Barcan formula are considered and proved complete in a uniform way. Completeness theorems are also shown for systems with the extended Barcan rule as well as for some quantified extensions of the modal logic B. (...) The incompleteness of Q°.B + BF is also proved. (shrink)

This paper investigates a first-order extension of GL called \. We outline briefly the history that led to \, its key properties and some of its toolbox: the \emph{conservation theorem}, its cut-free Gentzenisation, the ``formulators'' tool. Its semantic completeness is fully stated in the current paper and the proof is retold here. Applying the Solovay technique to those models the present paper establishes its main result, namely, that \ is arithmetically complete. As expanded below, \ is a first-order modal (...) logic that along with its built-in ability to simulate general classical first-order provability―"\" simulating the the informal classical "\"―is also arithmetically complete in the Solovay sense. (shrink)

This paper sets out a new way of combining Kripke-complete modal logics: lexicographic product. It discusses some basic properties of the lexicographic product construction and proves axiomatization/completeness results.

We prove frame determination results for the family of many-valued modal logics introduced by M. Fitting in the early '90s. Each modal language of this family is based on a Heyting algebra, which serves as the space of truth values, and is interpreted on an interesting version of possible-worlds semantics: the modal frames are directed graphs whose edges are labelled with an element of the underlying Heyting algebra. We introduce interesting generalized forms of the classical axioms D, (...) T, B, 4, and 5 and prove that they are canonical for certain algebraic frame properties, which generalize seriality, reflexivity, symmetry, transitivity and euclideanness. Our results are quite general as they hold for any modal language built on a complete Heyting algebra. (shrink)