Products of ‘transitive” modal logics

David Gabelaia, Agi Kurucz, Frank Wolter, Michael Zakharyaschev

Journal of Symbolic Logic · 2005 · 45 citations · 29 references

Concepts

Abstract

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 as K4 , S4 , S4.1 , K4.3 , GL , or Grz are 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, if l 1 and l 2 are classes of transitive frames such that their depth cannot be bounded by any fixed n < ω, then the logic of the class {5ℑ 1 × ℑ 2 ∣ ℑ 1 ∈ l 1 , ℑ 2 , ∈ l 2 } is undecidable. (On the contrary, the product of, say, K4 and the logic of all transitive Kripke frames of depth ≤ n , for some fixed n < ω, is decidable.) The complexity of these undecidable logics ranges from r.e. to co-r.e. and Π 1 1 -complete. As a consequence, we give the first known examples of Kripke incomplete commutators of Kripke complete logics.

References

29