We generalize and extend the class of Sahlqvist formulae in arbitrary polyadic modal languages, to the class of so called inductive formulae. To introduce them we use a representation of modal polyadic languages in a combinatorial style and thus, in particular, develop what we believe to be a better syntactic approach to elementary canonical formulae altogether. By generalizing the method of minimal valuations à la Sahlqvist–van Benthem and the topological approach of Sambin and Vaccaro we prove that all inductive formulae (...) are elementary canonical and thus extend Sahlqvist’s theorem over them. In particular, we give a simple example of an inductive formula which is not frame-equivalent to any Sahlqvist formula. Then, after a deeper analysis of the inductive formulae as set-theoretic operators in descriptive and Kripke frames, we establish a somewhat stronger model-theoretic characterization of these formulae in terms of a suitable equivalence to syntactically simpler formulae in the extension of the language with reversive modalities. Lastly, we study and characterize the elementary canonical formulae in reversive languages with nominals, where the relevant notion of persistence is with respect to discrete frames. (shrink)

We consider some modal languages with a modal operator D whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...) algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras. Other instances of this approach are looked at, and include the step by step method. (shrink)

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.

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)

We consider some modal languages with a modal operator $D$ whose semantics is based on the relation of inequality. Basic logical properties such as definability, expressive power and completeness are studied. Also, some connections with a number of other recent proposals to extend the standard modal language are pointed at.

We study a modal system ¯T, that extends the classical (prepositional) modal system T and whose language is provided with modal operators M inn (nN) to be interpreted, in the usual kripkean semantics, as there are more than n accessible worlds such that.... We find reasonable axioms for ¯T and we prove for it completeness, compactness and decidability theorems.

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.

These notes are a corrected and revised version of notes which accompanied lectures given at the Banach Center in the fall of 1991. The intent is to give a self-contained introduction to cylindric algebras from the concrete point of view. I hope that after reading this introduction the reader will be able to digest the basic works on this subject results about them as we go along. And we will try to motivate the notions from logic. See the end of (...) these notes for indices of symbols and words.Cylindric algebras form the most developed form of algebraic logic. In general, algebraic logic is concerned with algebraic structures which correspond to logics of various sorts. Cylindric algebras correspond to ordinary first order logics and to certain straightforward modifications of these logics. Other algebraic structures have a similar relationship to first order logic; the most developed of these are relation algebras and polyadic algebras. We will not be concerned with these, but the reader should be able to study them more easily after reading these notes.We will describe only the concrete aspect of cylindric algebras. The axiomatic version, fully developed in Henkin, Monk, Tarski [19], will play only a minor role. Also, we will not deal with applications. Such applications exist in several other fields, such as combinatorics and theoretical computer science.We assume familiarity with the elementary theory of Boolean algebras, elementary first order logic, and with the basics of universal algebra. (shrink)

The paper studies many-dimensional modal logics corresponding to products of Kripke frames. It proves results on axiomatisability, the finite model property and decidability for product logics, by applying a rather elaborated modal logic technique: p-morphisms, the finite depth method, normal forms, filtrations. Applications to first order predicate logics are considered too. The introduction and the conclusion contain a discussion of many related results and open problems in the area.

We study a modal system $\overline{T}$, that extends the classical modal system T and whose language is provided with modal operators $M_{n}$ to be interpreted, in the usual kripkean semantics, as "there are more than n accessible worlds such that...". We find reasonable axioms for $\overline{T}$ and we prove for it completeness, compactness and decidability theorems.

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.

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n >3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the following construction. From an arbitrary (...) undirected, loop-free graph Γ, we construct an n-dimensional atom structure E(Γ), and prove, for infinite Γ, that E(Γ) is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs (k < ω)with infinite chromatic number, but having a non-principal ultraproduct $\prod _D\Gamma _k $ whose chromatic number is just two. It follows that $E(\Gamma _k )$ is strongly representable (each k < ω) but $\Pi _D E(\Gamma _k)$ is not. (shrink)

We characterize the modal logics of elementary classes of Kripke frames as precisely those modal logics that are axiomatized by modal axioms synthesized in a certain effective way from "quasi-positive" sentences of hybrid logic. These are pure positive hybrid sentences with arbitrary existential and relativized universal quantification over nominals. The proof has three steps. The first step is to use the known result that the modal logic of any elementary class of Kripke frames is also the modal logic of the (...) closure of this class under disjoint unions, generated subframes, bounded morphic images, and ultraroots. This latter class can be defined by the first-order sentences of a special syntactic form (called pseudo-equations by Goldblatt) that are valid in the former class. The second step is to translate these pseudo-equations into equivalent quasi-positive hybrid sentences. In the third and main step, we show that any quasi-positive sentence S generates an infinite set of modal formulas called "approximants," which together axiomatize a canonical modal logic that is sound and complete for the class of frames validating S. The proof is analogous to standard proofs of Sahlqvist's theorem. It generalizes to sets of quasi-positive sentences. The main result now follows. (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.

We show the first examples of recursively enumerable (even decidable) two-dimensional products of finitely axiomatisable modal logics that are not finitely axiomatisable. In particular, we show that any axiomatisation of some bimodal logics that are determined by classes of product frames with linearly ordered first components must be infinite in two senses: It should contain infinitely many propositional variables, and formulas of arbitrarily large modal nesting-depth.