Abstract

We solve a major open problem concerning algorithmic properties of products of ‘transitive’ modal logics by showing that products and commutators of such standard logics asK4,S4,S4.1,K4.3,GL, orGrzare undecidable and do not have the finite model property. More generally, we prove that no Kripke complete extension of the commutator [K4, K4] with product frames of arbitrary finite or infinite depth (with respect to both accessibility relations) can be decidable. In particular, ifl1andl2are classes of transitive frames such that their depth cannot be bounded by any fixedn< ω, then the logic of the class {5ℑ1× ℑ2∣ ℑ1∈l1, ℑ2, ∈l2} is undecidable. (On the contrary, the product of, say,K4and the logic of all transitive Kripke frames of depth ≤n, for some fixedn< ω, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and Π11-complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.