We discuss a `negative' way of defining frame classes in (multi)modal logic, and address the question of whether these classes can be axiomatized by derivation rules, the `non-ξ rules', styled after Gabbay's Irreflexivity Rule. The main result of this paper is a metatheorem on completeness, of the following kind: If Λ is a derivation system having a set of axioms that are special Sahlqvist formulas and Λ+ is the extension of Λ with a set of non-ξ rules, then Λ+ is (...) strongly sound and complete with respect to the class of frames determined by the axioms and the rules. (shrink)

We investigate transfer of interpolation in such combinations of modal logic which lead to interaction of the modalities. Combining logics by taking products often blocks transfer of interpolation. The same holds for combinations by taking unions, a generalization of Humberstone's inaccessibility logic. Viewing first-order logic as a product of modal logics, we derive a strong counterexample for failure of interpolation in the finite variable fragments of first-order logic. We provide a simple condition stated only in terms of frames and bisimulations (...) which implies failure of interpolation. Its use is exemplified in a wide range of cases. (shrink)

In [STU 00, KUT 03] we introduced a family of ‘modal' languages intended for talking about distances. These languages are interpreted in ‘distance spaces' which satisfy some of the standard axioms of metric spaces. Among other things, we singled out decidable logics of distance spaces and proved expressive completeness results relating classical and modal languages. The aim of this paper is to axiomatize the modal fragments of the semantically defined distance logics of [KUT 03] and give a new proof of (...) their decidability. (shrink)

A certain type of inference rules in modal logics, generalizing Gabbay's Irreflexivity rule, is introduced and some general completeness results about modal logics axiomatized with such rules are proved.

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 propose a logic for reasoning about metric spaces with the induced topologies. It combines the 'qualitative' interior and closure operators with 'quantitative' operators 'somewhere in the sphere of radius r.' including or excluding the boundary. We supply the logic with both the intended metric space semantics and a natural relational semantics, and show that the latter (i) provides finite partial representations of (in general) infinite metric models and (ii) reduces the standard '∈-definitions' of closure and interior to simple constraints (...) on relations. These features of the relational semantics suggest a finite axiomatisation of the logic and provide means to prove its EXPTIME-completeness (even if the rational numerical parameters are coded in binary). An extension with metric variables satisfying linear rational (in)equalities is proved to be decidable as well. Our logic can be regarded as a 'well-behaved' common denominator of logical systems constructed in temporal, spatial, and similarity-based quantitative and qualitative representation and reasoning. Interpreted on the real line (with its Euclidean metric), it is a natural fragment of decidable temporal logics for specification and verification of real-time systems. On the real plane, it is closely related to quantitative and qualitative formalisms for spatial representation and reasoning, but this time the logic becomes undecidable. (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.

The author's motivation for constructing the calculi of this paper\nis so that time and tense can be "discussed together in the same\nlanguage" (p. 282). Two types of enriched propositional caluli for\ntense logic are considered, both containing ordinary propositional\nvariables for which any proposition may be substituted. One type\nalso contains "clock-propositional" variables, a,b,c, etc., for\nwhich only clock-propositional variables may be substituted and that\ncorrespond to instants or moments in the semantics. The other type\nalso contains "history-propositional" variables, u,v,w, etc., for\nwhich only history-propositional variables may (...) be substituted and\nthat correspond to maximally linearly ordered subsets of instants.\nThis second type is for tense logics in which time is not linear\nand where at any moment there may exist alternative future courses\nof events. Quantifiers are included in both types but only for clock-\nand history-propositional variables. However, these quantifiers are\ngiven an essentially substitutional interpretation. In addition,\nbesides each clock-propositional variable being true at exactly one\ninstant, the semantics requires that for each instant there be at\nleast one clock-propositional variable true at that instant, which\nin effect amounts to having each instant of the model "denoted" in\nthe formalism by some clock-propositional variable. Thus it is not\nsurprising that quantification over clock-propositional variables\nturns out to have a "well behaved first-order semantics" (p. 284).\n{One axiom relating history- with clock-propositions seems to need\nrevision: CKTauTbuAUabUba. Since the clock-propositional variables\nmight be true at the same instant the consequent should include an\nalternative, namely, LCab.} Besides the standard truth-functional\nand tense operators G,H,F,P, the author includes L for "it is\nalways the case that". The model-theoretic earlier-than relation\nordering instants and the semantic truth-at (an instant) relation\nare formalized by Uab and Taα (for a wff α) which\nare defined respectively as LCbPa (whenever the clock-proposition\nb is the case the clock-proposition a was the case) and LCaα\n(α is the case whenever the clock-proposition a is the case).\nBecause the future tense operators are definable in terms of U\nand T and the latter are definable in terms of L and P, the\ndual of H, the author notes that his completeness proofs can be\nrestricted to L and H as primitive and with the future tense\noperators used for other interpretations, especially Prior, A.'s\nindeterminist "it will be the case that", where time is not linear.\nThe author concludes with some rather technical observations showing\nthat "in ordinary tense logics the instants are nonstandard elements\nof the models. This provides", according to the author, "a semantic\npressure to build the instants into tense logic, so that they will\nappear as standard elements in the models" (p. 283). (shrink)

Hybridization is a method invented by Arthur Prior for extending the expressive power of modal languages. Although developed in interesting ways by Robert Bull, and by the Sofia school , the method remains little known. In our view this has deprived temporal logic of a valuable tool.The aim of the paper is to explain why hybridization is useful in temporal logic. We make two major points, the first technical, the second conceptual. First, we show that hybridization gives rise to well-behaved (...) logics that exhibit an interesting synergy between modal and classical ideas. This synergy, obvious for hybrid languages with full first-order expressive strength, is demonstrated for a weaker local language capable of defining the Until operator; we provide a minimal axiomatization, and show that in a wide range of temporally interesting cases extended completeness results can be obtained automatically. Second, we argue that the idea of sorted atomic symbols which underpins the hybrid enterprise can be developed further. To illustrate this, we discuss the advantages and disadvantages of a simple hybrid language which can quantify over paths. (shrink)

Several extensions of the basic modal language are characterized in terms of interpolation. Our main results are of the following form: Language ℒ' is the least expressive extension of ℒ with interpolation. For instance, let ℳ be the extension of the basic modal language with a difference operator [7]. First-order logic is the least expressive extension of ℳ with interpolation. These characterizations are subsequently used to derive new results about hybrid logic, relation algebra and the guarded fragment.

Over the last twenty years, in all of these neighbouring fields, modal systems have been developed that we call multi-dimensional. (Our definition of multi ...