Properties of Tense Logics

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. Mathematics Subject Classification: 03B45, 03B25.     

Exhibiting Wide Families of Maximal Intermediate Propositional Logics with the Disjunction Property

We provide results allowing to state, by the simple inspection of suitable classes of posets (propositional Kripke frames), that the corresponding intermediate propositional logics are maximal among the ones which satisfy the disjunction property. Starting from these results, we directly exhibit, without using the axiom of choice, the Kripke frames semantics of 2^No maximal intermediate propositional logics with the disjunction property. This improves previous evaluations, giving rise to the same conclusion but made with an essential use of the axiom of choice, of the cardinality of the set of the maximal intermediate propositional logics with the disjunction property. Mathematics Subject Classification: 03B55, 03C90.     

Kripke‐style semantics for many‐valued logics

This paper deals with Kripke‐style semantics for many‐valued logics. We introduce various types of Kripke semantics, and we connect them with algebraic semantics. As for modal logics, we relate the axioms of logics extending MTL to properties of the Kripke frames in which they are valid. We show that in the propositional case most logics are complete but not strongly complete with respect to the corresponding class of complete Kripke frames, whereas in the predicate case there are important many‐valued logics like BL, ? and Π, which are not even complete with respect to the class of all predicate Kripke frames in which they are valid. Thus although very natural, Kripke semantics seems to be slightly less powerful than algebraic semantics. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Decidability results in non-classical logic. III

A Kripke type semantics is given to a large class of tense logics with statability operators (including PriorsQK _t) in such a manner as to obtain their decidability using Rabin’s theorem. Dedicated to the Memory of A. N. Prior     

On intuitionistic modal and tense logics and their classical companion logics: Topological semantics and bisimulations

We take the well-known intuitionistic modal logic of Fischer Servi with semantics in bi-relational Kripke frames, and give the natural extension to topological Kripke frames. Fischer Servi’s two interaction conditions relating the intuitionistic pre-order (or partial-order) with the modal accessibility relation generalize to the requirement that the relation and its inverse be lower semi-continuous with respect to the topology. We then investigate the notion of topological bisimulation relations between topological Kripke frames, as introduced by Aiello and van Benthem, and show that their topology-preserving conditions are equivalent to the properties that the inverse relation and the relation are lower semi-continuous with respect to the topologies on the two models. The first main result is that this notion of topological bisimulation yields semantic preservation w.r.t. topological Kripke models for both intuitionistic tense logics, and for their classical companion multi-modal logics in the setting of the Gödel translation. After giving canonical topological Kripke models for the Hilbert-style axiomatizations of the Fischer Servi logic and its classical companion logic, we use the canonical model in a second main result to characterize a Hennessy–Milner class of topological models between any pair of which there is a maximal topological bisimulation that preserve the intuitionistic semantics.     

ON THE INADEQUACY OF THE RELATIONAL SEMANTIC FOR THE “UNTIL” OPERATOR

Modal logics with the binary operator Until are considered. It is shown that there exists a continuum of consistent U-logics without Kripke frames, and that each U-logic whose class of order does not have the finite frame property.     

Polymodal Lattices and Polymodal Logic

A polymodal lattice is a distributive lattice carrying an n-place operator preserving top elements and certain finite meets. After exploring some of the basic properties of such structures, we investigate their freely generated instances and apply the results to the corresponding logical systems — polymodal logics — which constitute natural generalizations of the usual systems of modal logic familiar from the literature. We conclude by formulating an extension of Kripke semantics to classical polymodal logic and proving soundness and completeness theorems. Mathematics Subject Classification: 03G10, 06D99, 03B45.     

All finitely axiomatizable subframe logics containing the provability logic CSM_{0} are decidable

In this paper we investigate those extensions of the bimodal provability logic (alias or which are subframe logics, i.e. whose general frames are closed under a certain type of substructures. Most bimodal provability logics are in this class. The main result states that all finitely axiomatizable subframe logics containing are decidable. We note that, as a rule, interesting systems in this class do not have the finite model property and are not even complete with respect to Kripke semantics. Received July 15, 1997     

Barwise's Information Frames and Modal Logics

The article studies Barwise's information frames and settles the problem of Barwise dealing in finding axiomatizations for the modal logics generated by information frames. We find axiomatic systems for: (i) the modal logic of all complete information frames; (ii) the logic of all sound and complete information frames; (iii) the logic of all hereditary and complete information frames; (iv) the logic of all complete, sound, and hereditary information frames; (v) the logic of all consistent and complete information frames. The notion of weak modal logics is also proposed, and it is shown that the weak modal logics generated by all information frames and by all hereditary information frames are K and K4, respectively. Toward a general theory, we prove that any Kripke complete modal logic is a modal logic of a certain class of information frames, and that every modal logic generated by any given class of complete, rarefied, and fully classified information frames is Kripke complete.     

Cut‐elimination Theorems for Some Infinitary Modal Logics

In this article, a cut‐free system TLM_ω1 for infinitary propositional modal logic is proposed which is complete with respect to the class of all Kripke frames.The system TLM_ω1 is a kind of Gentzen style sequent calculus, but a sequent of TLM_ω1 is defined as a finite tree of sequents in a standard sense. We prove the cut‐elimination theorem for TLM_ω1 via its Kripke completeness.     

Extending possibilistic logic over Gödel logic

In this paper we present several fuzzy logics trying to capture different notions of necessity (in the sense of possibility theory) for Gödel logic formulas. Based on different characterizations of necessity measures on fuzzy sets, a group of logics with Kripke style semantics is built over a restricted language, namely, a two-level language composed of non-modal and modal formulas, the latter, moreover, not allowing for nested applications of the modal operator N. Completeness and some computational complexity results are shown.     

Barwise's information frames and modal logics

 The paper studies Barwise's information frames and answers the John Barwise question: to find axiomatizations for the modal logics generated by information frames. We find axiomatic systems for (i) the modal logic of all complete information frames, (ii) the logic of all sound and complete information frames, (iii) the logic of all hereditary and complete information frames, (iv) the logic of all complete, sound and hereditary information frames, and (v) the logic of all consistent and complete information frames. The notion of weak modal logics is also proposed, and it is shown that the weak modal logics generated by all information frames and by all hereditary information frames are K and K4 respectively. To develop general theory, we prove that (i) any Kripke complete modal logic is the modal logic of a certain class of information frames and that (ii) the modal logic generated by any given class of complete, rarefied and fully classified information frames is Kripke complete. This paper is dedicated to the memory of talented mathematician John Barwise. Received: 7 May 2000 Published online: 10 October 2002 Key words or phrases: Knowledge presentation – Information – Information flow – Information frames – Modal logic-Kripke model     

On non‐compact logics in NEXT(KTB)

In this paper we construct a continuum of logics, extensions of the modal logic T₂ = KTB ⊕ □²p → □³p, which are non‐compact (relative to Kripke frames) and hence Kripke incomplete. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Intermediate predicate logic without the beth property

It is shown that a logic J _fd ^* characterized by all Kripke frames the domains of all nonmaximal worlds of which are finite lacks the Beth property. The logic is the first example of an intermediate superintuitionistic logic without the Beth property. The interpolation and the Beth properties are also proved missing in all predicate superintuitionistic logics which contain J _fd ^* and are contained in a logic characterized by frames of the form〈N _n , ≤,{Dk}k∈N n〉. Supported by the Russian Foundation for Humanities, grant No. 97-03-04089. Translated fromAlgebra i Logika, Vol. 37, No. 1, pp. 107–117, January–February, 1998.     

La connaissance commune en logique modale

The problem of Common Knowledge will be considered in two classes of models: a class K.* of Kripke models and a class S of Scott models. Two modal logic systems will be defined. Those systems, KC and MC, include an axiomatisation of Common Knowledge. We prove determination of each system by the corresponding class of models. MSC: 03B45, 68T25.     

A BRIEF SURVEY OF FRAMES FOR THE LAMBEK CALCULUS

Models for the Lambek calculus of syntactic categories surveyed here are based on frames that are in principle of the same type as Kripke frames for intuitionistic logic. These models are extracted from the literature on models for relevant logics, in particular the ternary relationed models introduced in the early seventies. The purpose of this brief survey is to locate some open completeness problems for variants of the Lambek calculus in the context of completeness results based on various types of ternary relational models.     

The Disjunction Property in the Class of Paraconsistent Extensions of Minimal Logic

We consider the disjunction property, DP, in the class of extensions of minimal logic L _j . Conditions are described under which DP is translated from the class PAR of properly paraconsistent extensions of the logics of class L _j into the class INT of intermediate extensions and the class NEG of negative extensions, and conditions for its being translated back into PAR. The logic L _F in PAR, which specifies conditions for DP to be translated from PAR into NEG, is defined and is characterized in terms of j-algebras and Kripke frames. Moreover, we show that L _F is decidable and possesses the disjunction property.     

All Finitely Axiomatizable Normal Extensions of K4.3 are Decidable

We use the apparatus of the canonical formulas introduced by Zakharyaschev [10] to prove that all finitely axiomatizable normal modal logics containing K4.3 are decidable, though possibly not characterized by classes of finite frames. Our method is purely frame-theoretic. Roughly, given a normal logic L above K4.3, we enumerate effectively a class of (possibly infinite) frames with respect to which L is complete, show how to check effectively whether a frame in the class validates a given formula, and then apply a Harropstyle argument to establish the decidability of L, provided of course that it has finitely many axioms.     

Submodels of Kripke models

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus. In Appendix A we prove that for theories with decidable identity we can take as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. Received: 4 February 1999 / Published online: 25 January 2001