A variety V of Boolean algebras with operators is singleton-persistent if it contains a complex algebra whenever it contains the subalgebra generated by the singletons. V is atom-canonical if it contains the complex algebra of the atom structure of any of the atomic members of V.This paper explores relationships between these "persistence" properties and questions of whether V is generated by its complex algebras or its atomic members, or is closed under canonical embedding algebras or completions. It also develops a (...) general theory of when operations involving complex algebras lead to the construction of elementary classes of relational structures. (shrink)

Sufficient syntactic conditions for canonicity in intermediate and intuitionistic modal logics are given. We present a new technique which does not require semantic first-order reduction and which is constructive in the sense that it works in an intuitionistic metatheory through a model without points which is classically isomorphic to the usual canonical model.

In this paper we present a general theory of normal forms, based on a categorial result for the free monoid construction. We shall use the theory mainly for proposictional modal logic, although it seems to have a wider range of applications. We shall formally represent normal forms as combinatorial objects, basically labelled trees and forests. This geometric conceptualization is implicit in and our approach will extend it to other cases and make it more direct: operations of a purely geometric and (...) combinatorial nature will be introduced in order to give a mathematical description of the basic logical/algebraic constructions .We begin by recalling the above-mentioned categorial construction: we need a careful inspection of it because in the various examples considered later we plan to deduce from it in a uniform way the normal forms and the description of finitely generated free algebras. This method always works whenever we can describe the category of algebras corresponding to the logic under consideration as a T-objects category. When this simple description seems not to be available, still the general theory might be of some interest, because a description of the category of algebras as a T-objects category plus equation is possible .The central part of the paper is more advanced and specific: we show how the general approach presented here can provide some insights even in the basic case of the modal system K. Section 4 contains a contribution to the theory of normal forms, namely the description of the uniform substitution. This result will enable us to give a duality theorem for the category of finitely generated free modal algebras and in Section 5 to provide a characterization of the collections of normal forms which happen to be normal forms for a logic, thus giving a description of the lattice of modal logics.Section 6 deals with some applications: we shall show how to use normal forms in order to prove for the modal system K the definability of higher-order propositional quantifiers and of the tense operator F .As to the prerequisites, the paper is almost self-contained. The reader is only assumed to have familiarity with standard techniques in algebraic logic ). Knowledge of the basic facts about adjoint functors is required too, see e.g. McLane or the appendix. (shrink)

We investigate an enrichment of the propositional modal language L with a "universal" modality ■ having semantics x ⊧ ■φ iff ∀y(y ⊧ φ), and a countable set of "names" - a special kind of propositional variables ranging over singleton sets of worlds. The obtained language ℒ $_{c}$ proves to have a great expressive power. It is equivalent with respect to modal definability to another enrichment ℒ(⍯) of ℒ, where ⍯ is an additional modality with the semantics x ⊧ ⍯φ (...) iff Vy(y ≠ x → y ⊧ φ). Model-theoretic characterizations of modal definability in these languages are obtained. Further we consider deductive systems in ℒ $_{c}$ . Strong completeness of the normal ℒ $_{c}$ logics is proved with respect to models in which all worlds are named. Every ℒ $_{c}$ -logic axiomatized by formulae containing only names (but not propositional variables) is proved to be strongly frame-complete. Problems concerning transfer of properties ([in]completeness, filtration, finite model property etc.) from ℒ to ℒ $_{c}$ are discussed. Finally, further perspectives for names in multimodal environment are briefly sketched. (shrink)

A definition and some inaccurate cross-references in the paper A Survey of Abstract Algebraic Logic, which might confuse some readers, are clarified and corrected; a short discussion of the main one is included. We also update a dozen of bibliographic references.

This paper reviews the impact of Rasiowa's well-known book on the evolution of algebraic logic during the last thirty or forty years. It starts with some comments on the importance and influence of this book, highlighting some of the reasons for this influence, and some of its key points, mathematically speaking, concerning the general theory of algebraic logic, a theory nowadays called Abstract Algebraic Logic. Then, a consideration of the diverse ways in which these key points can be generalized allows (...) us to survey some issues in the development of the field in the last twenty to thirty years. The last part of the paper reviews some recent lines of research that in some way transcend Rasiowa's approach. I hope in this way to give the reader a general view of Rasiowa's key position in the evolution of Algebraic Logic during the twentieth century. (shrink)

This paper presents duality results between categories of neighbourhood frames for modal logic and categories of modal algebras (i.e. Boolean algebras with an additional unary operation). These results extend results of Goldblatt and Thomason about categories of relational frames for modal logic.

Some results on the upper end of the lattice of all modal propositional logics.

The most common way of proving decidability in propositional modal logic is to shew that the system in question has the finite model property. This is not however the only way. Gabbay in [4] proves the decidability of many modal systems using Rabin's result in [8] on the decidability of the second-order theory of successor functions. In particular [4, pp. 258-265] he is able to prove the decidability of a system which lacks the finite model property. Gabbay's system is however (...) complete, in the sense of being characterized by a class of frames, and the question arises whether there is a decidable modal logic which is not complete. Since no incomplete modal logic has the finite model property [9, p. 33], any proof of decidability must employ some such method as Gabbay's. In this paper I use the Gabbay/Rabin technique to prove the decidability of a finitely axiomatized normal modal propositional logic which is not characterized by any class of frames. I am grateful to the referee for suggesting improvements in substance and presentation.The terminology I am using is standard in modal logic. By aframeis understood a pair 〈W, R〉 in whichWis a class (of “possible worlds”) andR⊆W2. To avoid confusion in what follows, a frame will henceforth be referred to as aKripkeframe. By contrast, ageneral frameis a pair 〈,Π〉 in whichis a Kripke frame andΠis a collection of subsets ofWclosed under the Boolean operations and satisfying the condition that ifAis inΠthen so isR−1“A. A model on a frame (of either kind) is obtained by adding a functionVwhich assigns sets of worlds to propositional variables. In the case of a general frame we require thatV(p) ∈Π. (shrink)

A well-known result, going back to the twenties, states that, under some reasonable assumptions, any logic can be characterized as the set of formulas satisfied by a matrix 〈,F〉, whereis an algebra of the appropriate type, andFa subset of the domain of, called the set of designated elements. In particular, every quasi-classical modal logic—a set of modal formulas, containing the smallest classical modal logicE, which is closed under the inference rules of substitution and modus ponens—is characterized by such a matrix, (...) wherenow is a modal algebra, andFis a filter of. If the modal logic is in fact normal, then we can do away with the filter; we can study normal modal logics in the setting of varieties of modal algebras. This point of view was adopted already quite explicitly in McKinsey and Tarski [8]. The observation that the lattice of normal modal logics is dually isomorphic to the lattice of subvarieties of a variety of modal algebras paved the road for an algebraic study of normal modal logics. The algebraic approach made available some general results from Universal Algebra, notably those obtained by Jónsson [6], and thereby was able to contribute new insights in the realm of normal modal logics [2], [3], [4], [10].The requirement that a modal logic be normal is rather a severe one, however, and many of the systems which have been considered in the literature do not meet it. For instance, of the five celebrated modal systems, S1–S5, introduced by Lewis, S4 and S5 are the only normal ones, while only SI fails to be quasi-classical. The purpose of this paper is to generalize the algebraic approach so as to be applicable not just to normal modal logics, but to quasi-classical modal logics in general. (shrink)

We shall describe the set of strongly meet irreducible logics in the lattice ϵLin.t of normal tense logics of weak orderings. Based on this description it is shown that all logics in ϵLin.t are independently axiomatizable. Then the description is used in order to investigate tense logics with respect to decidability, finite axiomatizability, axiomatization problems and completeness with respect to Kripke semantics. The main tool for the investigation is a translation of bimodal formulas into a language talking about partitions of (...) general frames into intervals so that relative to both Kripke frames and descriptive frames the expressive power of both languages coincides. (shrink)

Based on the results of [11] this paper delivers uniform algorithms for deciding whether a finitely axiomatizable tense logic has the finite model property, is complete with respect to Kripke semantics, is strongly complete with respect to Kripke semantics, is d-persistent, is r-persistent.It is also proved that a tense logic is strongly complete iff the corresponding variety of bimodal algebras is complex, and that a tense logic is d-persistent iff it is complete and its Kripke frames form a first order (...) definable class. From this we obtain many natural non-d-persistent tense logics whose corresponding varieties of bimodal algebras are complex. (shrink)

Modern modal logic originated as a branch of philosophical logic in which the concepts of necessity and possibility were investigated by means of a pair of dual operators that are added to a propositional or first-order language. The field owes much of its flavor and success to the introduction in the 1950s of the “possible-worlds” semantics in which the modal operators are interpreted via some “accessibility relation” connecting possible worlds. In subsequent years, modal logic has received attention as an attractive (...) approach towards formalizing such diverse notions as time, knowledge, or action. Nowadays, modal logics are applied in various disciplines, ranging from economics to linguistics and computer science. Consequently, there is by now a large variety of modal languages, with an even greater wealth of interpretations. For instance, many applications require a poly-modal framework consisting of a language with a family of modal operators and a semantics in which the corresponding accessibility relations are connected somehow. (shrink)

We define a nontrivial variety of boolean algebras with operators such that every member of the variety is atomless. This shows that not every variety of boolean algebras with operators is generated by its atomic members, and thus establishes a strong incompleteness result in (multi-)modal logic.

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

Although we believe the results reported below to have direct philosophical import, we shall for the most part confine our remarks to the realm of mathematics. The reader is referred to [4] for a philosophically oriented discussion, comprehensible to mathematicians, of tense logic.The “minimal” tense logicT0is the system having connectives ∼, →,F(“at some future time”), andP(“at some past time”); the following axioms:(whereGandHabbreviate ∼F∼ and ∼P∼ respectively); and the following rules:(8) fromαandα → β, inferβ,(9) fromα, infer any substitution instance ofα,(10) fromα, (...) inferGα,(11) fromα, inferHα.A tense logic is a systemTwhose language is that ofT0and whose axioms and rules include (1)–(11). The axioms and rules ofTother than (1)–(11) are calledproperaxioms and rules.We shall investigate three systems of semantics for tense logics, i.e. three notions ofstructureand three relations ⊧ which stand between structures and formulas. One reads⊧αas “αis valid in.” A structureis amodelof a tense logicTif every formula provable inTis valid in. A semantics isadequateforTif the set of models ofTin the semantics is characteristic forT, i.e. if wheneverT ∀ αthen there is a modelofTin the semantics such that∀ α. Two structuresand, possibly from different semantics, are calledequivalent(∼) if exactly the same formulas are valid inas in. (shrink)

In this paper, we extend the canonicity methodology in Ghilardi & Meloni (1997) to arbitrary lattice expansions, and syntactically describe canonical inequalities for lattice expansions consisting of -meet preserving operations, -multiplicative operations, adjoint pairs, and constants. This approach gives us a uniform account of canonicity for substructural and lattice-based logics. Our method not only covers existing results, but also systematically accounts for many canonical inequalities containing nonsmooth additive and multiplicative uniform operations. Furthermore, we compare our technique with the approach in (...) Dunn et al. (2005) and Gehrke et al. (2005). (shrink)

This paper looks at the concept of neighborhood canonicity introduced by BRIAN CHELLAS [2]. We follow the lead of the author's paper [9] where it was shown that every non-iterative logic is neighborhood canonical and here we will show that all logics whose axioms have a simple syntactic form-no intensional operator is in boolean combination with a propositional letter-and which have the finite model property are neighborhood canonical. One consequence of this is that KMcK, the McKinsey logic, is neighborhood canonical, (...) an interesting counterpoint to the results of ROBERT GOLDBLATT and XIAOPING WANG who showed, respectively, that KMcK is not relational canonical [5] and that KMcK is not relationally strongly complete [11]. (shrink)

We present our personal view on W.J. Blok's contribution to modal logic.

This paper obtains the weak completeness and decidability results for standard systems of modal logic using models built from formulas themselves. This line of work began with Fine (Notre Dame J. Form. Log. 16:229-237, 1975). There are two ways in which our work advances on that paper: First, the definition of our models is mainly based on the relation Kozen and Parikh used in their proof of the completeness of PDL, see (Theor. Comp. Sci. 113-118, 1981). The point is to (...) develop a general model-construction method based on this definition. We do this and thereby obtain the completeness of most of the standard modal systems, and in addition apply the method to some other systems of interest. None of the results use filtration, but in our final section we explore the connection. (shrink)

In this paper, we are going to analyze the phenomenon of modal incompleteness from an algebraic point of view. The usual method of showing that a given logic L is incomplete is to show that for some L and some cannot be separated from by a suitably wide class of complete algebras — usually Kripke algebras. We are going to show that classical examples of incomplete logics, e.g., Fine logic, are not complete with respect to any class of complete BAOs. (...) Even above Grz it is possible to find a continuum of such logics, which immediately implies the existence of a continuum of neighbourhood-incomplete Grz logics. Similar results can be proved for Löb logics. In addition, completely incomplete logics above Grz may be found uniformly as a result of failures of some admissible rule of a special kind. (shrink)

We prove that all finitely axiomatizable tense logics with temporal operators for ‘always in the future’ and ‘always in the past’ and determined by linear fows time are coNP-complete. It follows, for example, that all tense logics containing a density axiom of the form ■n+1F p → nF p, for some n ≥ 0, are coNP-complete. Additionally, we prove coNP-completeness of all ∩-irreducible tense logics. As these classes of tense logics contain many Kripke incomplete bimodal logics, we obtain many natural (...) examples of Kripke incomplete normal bimodal logics which are nevertheless coNP-complete. (shrink)