This paper considers proof-theoretic semantics for necessity within Dummett's and Prawitz's framework. Inspired by a system of Pfenning's and Davies's, the language of intuitionist logic is extended by a higher order operator which captures a notion of validity. A notion of relative necessary is defined in terms of it, which expresses a necessary connection between the assumptions and the conclusion of a deduction.

Scroggs's theorem on the extensions of S5 is an early landmark in the modern mathematical studies of modal logics. From it, we know that the lattice of normal extensions of S5 is isomorphic to the inverse order of the natural numbers with infinity and that all extensions of S5 are in fact normal. In this paper, we consider extending Scroggs's theorem to modal logics with propositional quantifiers governed by the axioms and rules analogous to the usual ones for ordinary quantifiers. (...) We call them Π-logics. Taking S5Π, the smallest normal Π-logic extending S5, as the natural counterpart to S5 in Scroggs's theorem, we show that all normal Π-logics extending S5Π are complete with respect to their complete simple S5 algebras, that they form a lattice that is isomorphic to the lattice of the open sets of the disjoint union of two copies of the one-point compactification of N, that they have arbitrarily high Turing-degrees, and that there are non-normal Π-logics extending S5Π. (shrink)

In this paper we use “generic submodels” to prove that each normal extension of G.3 (K4.3W) has the finite model property, by which we establish that each proper normal extension of G.3 is G.3Altn for some n≥0.

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)

The logic of 'elsewhere,' i.e., of a sentence operator interpretable as attaching to a formula to yield a formula true at a point in a Kripke model just in case the first formula is true at all other points in the model, has been applied in settings in which the points in question represent spatial positions, as well as in the case in which they represent moments of time. This logic is applied here to the alethic modal case, in which (...) the points are thought of as possible worlds, with the suggestion that its deployment clarifies aspects of a position explored by John Divers under the name 'modal agnosticism.' In particular, it makes available a logic whose Halldén incompleteness explicitly registers the agnostic element of the position - its neutrality as between modal realism and modal anti-realism. (shrink)

We establish the dichotomy property for stable canonical multi-conclusion rules for IPC, K4, and S4. This yields an alternative proof of existence of explicit bases of admissible rules for these logics.

In this paper we provide frame definability results for weak versions of classical modal axioms that can be expressed in Fitting's many-valued modal languages. These languages were introduced by M. Fitting in the early '90s and are built on Heyting algebras which serve as the space of truth values. The possible-worlds frames interpreting these languages are directed graphs whose edges are labelled with an element of the underlying Heyting algebra, providing us a form of many-valued accessibility relation. Weak axioms of (...) the form we treat here have been examined from the completeness perspective and further explored for applications in non-monotonic reasoning. Here, we introduce more weak many-valued modal axioms and prove a frame correspondence result for all of them. The classes of corresponding labelled frames possess algebraic properties which are strongly reminiscent of many classical ones, such as the Church-Rosser property, reflexivity, transitivity, partial functionality, etc. (shrink)

We show that for finite n⩾3n⩾3, every first-order axiomatisation of the varieties of representable n-dimensional cylindric algebras, diagonal-free cylindric algebras, polyadic algebras, and polyadic equality algebras contains an infinite number of non-canonical formulas. We also show that the class of structures for each of these varieties is non-elementary. The proofs employ algebras derived from random graphs.

This paper proves the finite model property and the finite axiomatizability of a class of normal modal logics extending K4.3. The frames for these logics are those for K4.3, in each of which every point has a bounded number of irreflexive successors if it is after an infinite ascending chain of (not necessarily distinct) points.

While monadic second-order logic (MSO) has played a prominent role in model theoretic syntax, modal logics have been used in this context since its inception. When comparing propositional dynamic logic (PDL) to MSO over trees, Kracht (1997) noted that there are tree languages that can be defined in MSO that can only be defined in PDL by adding new features whose distribution is predictable. He named such features “inessential features”. We show that Kracht’s observation can be extended to other modal (...) logics of trees in two ways. First, we demonstrate that for each stronger logic, there exists a tree language that can only be defined in a weaker logic with inessential features. Second, we show that any tree language that can be defined in a stronger logic, but not in some weaker logic, can be defined with inessential features. Additionally, we consider Kracht’s definition of inessential features more closely. It turns out that there are features whose distribution can be predicted, but who fail to be inessential in Kracht’s sense. We will look at ways to modify his definition. (shrink)

We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...) Thomason). The constructions use the result of Erd $\H{o}$ s that there are finite graphs with arbitrarily large chromatic number and girth. (shrink)

This book provides a detailed exposition of one of the most practical and popular methods of proving theorems in logic, called Natural Deduction. It is presented both historically and systematically. Also some combinations with other known proof methods are explored. The initial part of the book deals with Classical Logic, whereas the rest is concerned with systems for several forms of Modal Logics, one of the most important branches of modern logic, which has wide applicability.

The Moral Law is fulfilled iff everything that ought to be the case is the case, and The Good is realised in a possible world w at a time t iff w is deontically accessible from w at t. In this paper, I will introduce a set of temporal modal deontic systems with propositional quantifiers that can be used to prove some interesting theorems about The Moral Law and The Good. First, I will describe a set of systems without any (...) propositional quantifiers. Then, I will show how these systems can be extended by a couple of propositional quantifiers. I will use a kind of TxW semantics to describe the systems semantically and semantic tableaux to describe them syntactically. Every system will include a constant · that stands for The Good. ‘·’ is read as ‘The Good is realised’. All systems that contain the propositional quantifiers will also include a constant '*' that stands for The Moral Law. '*' is read as ‘The Moral Law is fulfilled’. I will prove that all systems (without the propositional quantifiers) are sound and complete with respect to their semantics and that all systems (including the extended systems) are sound with respect to their semantics. It is left as an open question whether or not the extended systems are complete. (shrink)

We provide syntactic necessary and sufficient conditions on the formulae reducible by the second-order quantifier elimination algorithm DLS. It is shown that DLS is compete for all modal Sahlqvist and Inductive formulae, and that all modal formulae in a single propositional variable on which DLS succeeds are canonical.

In this paper we define and examine frame constructions for the family of manyvalued modal logics introduced by M. Fitting in the '90s. Every language of this family is built on an underlying space of truth values, a Heyting algebra H. We generalize Fitting's original work by considering complete Heyting algebras as truth spaces and proceed to define a suitable notion of H-indexed families of generated subframes, disjoint unions and bounded morphisms. Then, we provide an algebraic generalization of the canonical (...) extension of a frame and model, and prove a preservation result inspired from Fitting's canonical model argument in [FIT 92a]. The analog of a complex algebra and of a principal ultrafilter is defined and the embedding of a frame into its canonical extension is presented. (shrink)

This papers gives a survey of recent results about simulations of one class of modal logics by another class and of the transfer of properties of modal logics under extensions of the underlying modal language. We discuss: the transfer from normal polymodal logics to their fusions, the transfer from normal modal logics to their extensions by adding the universal modality, and the transfer from normal monomodal logics to minimal tense extensions. Likewise, we discuss simulations of normal polymodal logics by normal (...) monomodal logics, of nominals and the difference operator by normal operators, of monotonic monomodal logics by normal bimodal logics, of polyadic normal modal logics by polymodal normal modal logics, and of intuitionistic modal logics by normal bimodal logics. (shrink)

Weakly Aggregative Modal Logic ) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. \ has interesting applications on epistemic logic, deontic logic, and the logic of belief. In this paper, we study some basic model theoretical aspects of \. Specifically, we first give a van Benthem–Rosen characterization theorem of \ based on an intuitive notion of bisimulation. Then, in contrast to many well known normal or non-normal modal logics, we show that (...) each basic \ system \ lacks Craig interpolation. Finally, by model theoretical techniques, we show that an extension of \ does have Craig interpolation, as an example of amending the interpolation problem of \. (shrink)

A finitely alternative normal tense logic \ is a normal tense logic characterized by frames in which every point has at most n future alternatives and m past alternatives. The structure of the lattice \\) is described. There are \ logics in \\) without the finite model property, and only one pretabular logic in \\). There are \ logics in \\) which are not finitely axiomatizable. For \, there are \ logics in \\) without the FMP, and infinitely many pretabular (...) extensions of \. (shrink)

In this paper, I will develop a set of boulesic-doxastic tableau systems and prove that they are sound and complete. Boulesic-doxastic logic consists of two main parts: a boulesic part and a doxastic part. By ‘boulesic logic’ I mean ‘the logic of the will’, and by ‘doxastic logic’ I mean ‘the logic of belief’. The first part deals with ‘boulesic’ concepts, expressions, sentences, arguments and theorems. I will concentrate on two types of boulesic expression: ‘individual x wants it to be (...) the case that’ and ‘individual x accepts that it is the case that’. The second part deals with ‘doxastic’ concepts, expressions, sentences, arguments and theorems. I will concentrate on two types of doxastic expression: ‘individual x believes that’ and ‘it is imaginable to individual x that’. Boulesic-doxastic logic investigates how these concepts are related to each other. Boulesic logic is a new kind of logic. Doxastic logic has been around for a while, but the approach to this branch of logic in this paper is new. Each system is combined with modal logic with two kinds of modal operators for historical and absolute necessity and predicate logic with necessary identity and ‘possibilist’ quantifiers. I use a kind of possible world semantics to describe the systems semantically. I also sketch out how our basic language can be extended with propositional quantifiers. All the systems developed in this paper are new. (shrink)

The present paper is a study in abstract algebraic logic. We investigate the correspondence between the metalogical Beth property and the algebraic property of surjectivity of epimorphisms. It will be shown that this correspondence holds for the large class of equivalential logics. We apply our characterization theorem to relevance logics and many-valued logics.

We give a reading of binary necessity statements of the form “ϕ is necessary for ψ” in terms of proofs. This reading is based on the idea of interpreting such statements as “Every proof of ψ uses ϕ”.

We study a canonical modal logic introduced by Lemmon, and axiomatised by an infinite sequence of axioms generalising McKinsey’s formula. We prove that the class of all frames for this logic is not closed under elementary equivalence, and so is non-elementary. We also show that any axiomatisation of the logic involves infinitely many non-canonical formulas.

In this paper I argue that a variety of consequence relations can be subsumed under a common core. The reduction proceeds by taking the unconditional consequence, or judgment, as basic and deriving the conditional consequence via a uniform abstraction scheme. A specific outcome is that it is better not to base such a scheme on the semantic notion of a matrix and valuation but rather on theories and substitutions. I will also briefly look at consequence relations that are not reducible (...) in this way. (shrink)

Three notions of definability in multimodal logic are considered. Two are analogous to the notions of explicit definability and implicit definability introduced by Beth in the context of first-order logic. However, while by Beth’s theorem the two types of definability are equivalent for first-order logic, such an equivalence does not hold for multimodal logics. A third notion of definability, reducibility, is introduced; it is shown that in multimodal logics, explicit definability is equivalent to the combination of implicit definability and reducibility. (...) The three notions of definability are characterized semantically using (modal) algebras. The use of algebras, rather than frames, is shown to be necessary for these characterizations. (shrink)

This volume is dedicated to Leo Esakia's contributions to the theory of modal and intuitionistic systems. Consisting of 10 chapters, written by leading experts, this volume discusses Esakia’s original contributions and consequent developments that have helped to shape duality theory for modal and intuitionistic logics and to utilize it to obtain some major results in the area. Beginning with a chapter which explores Esakia duality for S4-algebras, the volume goes on to explore Esakia duality for Heyting algebras and its generalizations (...) to weak Heyting algebras and implicative semilattices. The book also dives into the Blok-Esakia theorem and provides an outline of the intuitionistic modal logic KM which is closely related to the Gödel-Löb provability logic GL. One chapter scrutinizes Esakia’s work interpreting modal diamond as the derivative of a topological space within the setting of point-free topology. The final chapter in the volume is dedicated to the derivational semantics of modal logic and other related issues. (shrink)

The global consequence relation of a normal modal logic \ is formulated as a global sequent calculus which extends the local sequent theory of \ with global sequent rules. All global sequent calculi of normal modal logics admits global cut elimination. This property is utilized to show that decidability is preserved from the local to global sequent theories of any normal modal logic over \. The preservation of Craig interpolation property from local to global sequent theories of any normal modal (...) logic is shown by proof-theoretic method. (shrink)

The relationships between various modal logics based on Belnap and Dunn’s paraconsistent four-valued logic FDE are investigated. It is shown that the paraconsistent modal logic \, which lacks a primitive possibility operator \, is definitionally equivalent with the logic \, which has both \ and \ as primitive modalities. Next, a tableau calculus for the paraconsistent modal logic KN4 introduced by L. Goble is defined and used to show that KN4 is definitionally equivalent with \ without the absurdity constant. Moreover, (...) a tableau calculus is defined for the modal bilattice logic MBL introduced and investigated by A. Jung, U. Rivieccio, and R. Jansana. MBL is a generalization of BK that in its Kripke semantics makes use of a four-valued accessibility relation. It is shown that MBL can be faithfully embedded into the bimodal logic \ over the non-modal vocabulary of MBL. On the way from \ to MBL, the Fischer Servi-style modal logic \ is defined as the set of all modal formulas valid under a modified standard translation into first-order FDE, and \ is shown to be characterized by the class of all models for \. Moreover, \ is axiomatized and this axiom system is proved to be strongly sound and complete with respect to the class of models for \. Moreover, the notion of definitional equivalence is suitably weakened, so as to show that \ and \ are weakly definitionally equivalent. (shrink)

This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML (eXtensible Markup Language) documents, we revisit the language. This renewed interest (...) comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical (second-order) problems, like the boolean circuit and the frontier problem. (shrink)

This book offers a state-of-the-art introduction to the basic techniques and results of neighborhood semantics for modal logic. In addition to presenting the relevant technical background, it highlights both the pitfalls and potential uses of neighborhood models – an interesting class of mathematical structures that were originally introduced to provide a semantics for weak systems of modal logic. In addition, the book discusses a broad range of topics, including standard modal logic results ; bisimulations for neighborhood models and other model-theoretic (...) constructions; comparisons with other semantics for modal logic ; neighborhood semantics for first-order modal logic, applications in game theory ; applications in epistemic logic ; and non-normal modal logics with dynamic modalities. The book can be used as the primary text for seminars on philosophical logic focused on non-normal modal logics; as a supplemental text for courses on modal logic, logic in AI, or philosophical logic ; or as the primary source for researchers interested in learning about the uses of neighborhood semantics in philosophical logic and game theory. (shrink)

This study examines BDI logics in the context of Gabbay's fibring semantics. We show that dovetailing can be adopted as a semantic methodology to combine BDI logics. We develop a set of interaction axioms that can capture static as well as dynamic aspects of the mental states in BDI systems, using Catach's incestual schema G^[a, b, c, d]. Further we exemplify the constraints required on fibring function to capture the semantics of interactions among modalities. The advantages of having a fibred (...) approach is discussed in the final section. (shrink)

This paper investigates partitions of lattices of modal logics based on superintuitionistic logics which are defined by forming, for each superintuitionistic logic L and classical modal logic , the set L[] of L-companions of . Here L[] consists of those modal logics whose non-modal fragments coincide with L and which axiomatize if the law of excluded middle p V p is added. Questions addressed are, for instance, whether there exist logics with the disjunction property in L[], whether L[] contains a (...) smallest element, and whether L[] contains lower covers of . Positive solutions as concerns the last question show that there are (uncountably many) superclean modal logics based on intuitionistic logic in the sense of Vakarelov [28]. Thus a number of problems stated in [28] are solved. As a technical tool the paper develops the splitting technique for lattices of modal logics based on superintuitionistic logics and ap plies duality theory from [34]. (shrink)

This paper presents a generalization of Fine’s completeness theorem for transitive logics of finite width, and proves the Kripke completeness of transitive logics of finite “suc-eq-width”. The frame condition for each finite suc-eq-width axiom requires, in rooted transitive frames, a finite upper bound of cardinality for antichains of points with different proper successors. The paper also presents a generalization of Rybakov’s completeness theorem for transitive logics of prefinite width, and proves the Kripke completeness of transitive logics of prefinite “suc-eq-width”. The (...) frame condition for each prefinite suc-eq-width axiom requires, in rooted transitive frames, a finite upper bound of cardinality for antichains of points that have a finite lower bound of depth and have different proper successors. We will construct continuums of transitive logics of finite suc-eq-width but not of finite width, and continuums of those of prefinite suc-eq-width but not of prefinite width. This shows that our new completeness results cover uncountably many more logics than Fine’s theorem and Rybakov’s theorem respectively. (shrink)

The paper aims at studying, in full generality, logics defined by imposing a variable inclusion condition on a given logic $$\vdash $$. We prove that the description of the algebraic counterpart of the left variable inclusion companion of a given logic $$\vdash $$ is related to the construction of Płonka sums of the matrix models of $$\vdash $$. This observation allows to obtain a Hilbert-style axiomatization of the logics of left variable inclusion, to describe the structure of their reduced models, (...) and to locate them in the Leibniz hierarchy. (shrink)

We show that the lattices of the normal extensions of four well-known logics—propositional intuitionistic logic \, Grzegorczyk logic \, modalized Heyting calculus \ and \—can be joined in a commutative diagram. One connection of this diagram is an isomorphism between the lattices of the normal extensions of \ and \; we show some preservation properties of this isomorphism. Two other connections are join semilattice epimorphims of the lattice of the normal extensions of \ onto that of \ and of the (...) lattice of the normal extensions of \ onto that of \. The link between \ and \ is a well-known isomorphism established by the Blok–Esakia theorem. (shrink)

Sahlqvist formulas are a syntactically specified class of modal formulas proposed by Hendrik Sahlqvist in 1975. They are important because of their first-order definability and canonicity, and hence axiomatize complete modal logics. The first-order properties definable by Sahlqvist formulas were syntactically characterized by Marcus Kracht in 1993. The present paper extends Kracht's theorem to the class of ‘generalized Sahlqvist formulas' introduced by Goranko and Vakarelov and describes an appropriate generalization of Kracht formulas.

We study set algebras with an operator (SAO) that satisfy the axioms of S5 knowledge. A necessary and sufficient condition is given for such SAOs that the knowledge operator is defined by a partition of the state space. SAOs are constructed for which the condition fails to hold. We conclude that no logic singles out the partitional SAOs among all SAOs.

In this paper we consider the normal modal logics of elementary classes defined by first-order formulas of the form \. We prove that many properties of these logics, such as finite axiomatisability, elementarity, axiomatisability by a set of canonical formulas or by a single generalised Sahlqvist formula, together with modal definability of the initial formula, either simultaneously hold or simultaneously do not hold.

Modal logic is concerned with the analysis of sentential operators in the widest sense. Originally invented to analyse the notion of necessity applications have been found in many areas of philosophy, logic, linguistics and computer science. This in turn has led to an increased interest in the technical development of modal logic.

Description logics refer to a family of formalisms concentrated around concepts, roles and individuals. They belong to the most frequently used knowledge representation formalisms and provide a logical basis to a variety of well known paradigms. The main reasoning tasks considered in the area of description logics are those reducible to subsumption. On the other hand, any knowledge representation system should be equipped with a more advanced reasoning machinery. Therefore in the current paper we make a step towards integrating description (...) logics with second-order reasoning. One of the important motivations behind introducing second-order formalism follows from the fact that many forms of commonsense and nonmonotonic reasoning used in AI can be modelled within the second-order logic. To achieve our goal we first extend description logics with a possibility to quantify over concepts. Since one of the main criticisms against the use of second-order formalisms is their complexity, we next propose second-order quantifier elimination techniques applicable to a large class of description logic formulas. Finally we show applications of the techniques, in particular in reasoning with circumscribed concepts and approximated terminological formulas. (shrink)

Special issue: "Reflecting on the Legacy of C.I. Lewis: Contemporary and Historical Perspectives on Modal Logic".