Tense logics formulated in the bimodal propositional language are investigated with respect to Kripke-completeness (completeness) and decidability. It is proved that all minimal tense extensions of modal logics of finite width (in the sense of K. Kine) as well as all minimal tense extensions of cofinal subframe logics (in the sense of M. Zakharyaschev) are complete. The decidability of all finitely axiomatizable minimal tense extensions of cofinal subframe logics is shown. A number of variations and extensions of these results are (...) also presented. (shrink)

A new characterization of tabularity in tense logic is established, namely, a tense logic L is tabular if and only if $\mathsf {tab}_n^T\in L$ for some $n\geq 1$. Two characterization theorems for the Post-completeness in tabular tense logics are given. Furthermore, a characterization of the Post-completeness in the lattice of all tense logics is established. Post numbers of some tense logics are shown.

This paper investigates the structure of lattices of normal mono- and polymodal subframelogics, i.e., those modal logics whose frames are closed under a certain type of substructures. Nearly all basic modal logics belong to this class. The main lattice theoretic tool applied is the notion of a splitting of a complete lattice which turns out to be connected with the “geometry” and “topology” of frames, with Kripke completeness and with axiomatization problems. We investigate in detail subframe logics containing K4, those (...) containing polymodal Altn and subframe logics which are tense logics. (shrink)

We construct a normal extension of K4 with the finite model property whose minimal tense extension is not complete with respect to Kripke semantics.

We develop canonical rules capable of axiomatizing all systems of multiple-conclusion rules over K4 or IPC, by extension of the method of canonical formulas by Zakharyaschev [37]. We use the framework to give an alternative proof of the known analysis of admissible rules in basic transitive logics, which additionally yields the following dichotomy: any canonical rule is either admissible in the logic, or it is equivalent to an assumption-free rule. Other applications of canonical rules include a generalization of the Blok–Esakia (...) theorem and the theory of modal companions to systems of multiple-conclusion rules or (finitary structural global) consequence relations, and a characterization of splittings in the lattices of consequence relations over monomodal or superintuitionistic logics with the finite model property. (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)

In this paper we investigate those extensions of the bimodal provability logic ${\vec CSM}_{0}$ (alias ${\vec PRL}_{1}$ or ${\vec F}^{-})$ 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 ${\vec CSM}_{0}$ 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. (shrink)

In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of van Benthem, “Syntactic aspects of modal incompleteness theorems,” and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, ${\cal V}$-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves the open question (...) in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to ${\cal V}$-baos, namely the provability logic $GLB$. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is ${\cal V}$-complete. After these results, we generalize the Blok Dichotomy to degrees of ${\cal V}$-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness. (shrink)

It is proved that all bimodal tense logics which contain the logic of the weak orderings and have unbounded depth do not have the interpolation property.