Partitioning Kripke frames of finite height

A. V. Kudinov ; I. B. Shapirovsky

Izvestiya. Mathematics , Tome 81 (2017) no. 3, pp. 592-617.

Résumé

In this paper we prove the finite model property and decidability of a family of modal logics. A binary relation $R$ is said to be pretransitive if $R^*=\bigcup_{i\leqslant m} R^i$ for some $m\geqslant 0$, where $R^*$ is the transitive reflexive closure of $R$. By the height of a frame $(W,R)$ we mean the height of the preorder $(W,R^*)$. We construct special partitions (filtrations) of pretransitive frames of finite height, which implies the finite model property and decidability of their modal logics.

Détail

Keywords: modal logic, finite model property, decidability, finite height.
Mots-clés : pretransitive relation

Bibliographie

[1] The description logic handbook. Theory, implementation, and applications, eds. F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. Patel-Schneider, Cambridge Univ. Press, Cambridge, 2003, xviii+555 pp. | MR | Zbl

[2] M. Y. Vardi, “Automata-theoretic techniques for temporal reasoning”, Handbook of modal logic, Stud. Log. Pract. Reason., 3, Elsevier, Amsterdam, 2007, 971–989 | DOI

[3] V. Goranko, M. Otto, “Model theory of modal logic”, Handbook of modal logic, Stud. Log. Pract. Reason., 3, Elsevier, Amsterdam, 2007, 249–329 | DOI

[4] G. Boolos, The logic of provability, Cambridge Univ. Press, Cambridge, 1993, xxxvi+276 pp. | MR | Zbl

[5] R. M. Smullyan, M. Fitting, Set theory and the continuum problem, Oxford Logic Guides, 34, Oxford Univ. Press, New York, 1996, xiv+288 pp. | MR | Zbl

[6] Y. Venema, “Cylindric modal logic”, J. Symbolic Logic, 60:2 (1995), 591–623 | DOI | MR | Zbl

[7] C. I. Lewis, C. H. Langford, Symbolic logic, Century, New York–London, 1932, xi+506 pp. | MR | Zbl

[8] J. C. C. McKinsey, A. Tarski, “Some theorems about the sentential calculi of Lewis and Heyting”, J. Symbolic Logic, 13:1 (1948), 1–15 | DOI | MR | Zbl

[9] J. C. C. McKinsey, “A solution of the decision problem for the Lewis systems S2 and S4, with an application to topology”, J. Symbolic Logic, 6:4 (1941), 117–134 | DOI | MR | Zbl

[10] B. Jónsson, A. Tarski, “Boolean algebras with operators. I”, Amer. J. Math., 73:4 (1951), 891–939 | DOI | MR | Zbl

[11] V. A. Jankov, “Constructing a sequence of strongly independent superintuitionistic propositional calculi”, Soviet Math. Dokl., 9:1 (1968), 806–807 | MR | Zbl

[12] K. Gödel, “An interpretation of the intuitionistic propositional calculus”, with an introductory note by A. S. Troelstra, Collected works, v. I, Publications 1929–1936, Oxford Univ. Press, Oxford, 1986, 296–301 | MR | Zbl | Zbl

[13] R. M. Solovay, “Provability interpretations of modal logic”, Israel J. Math., 25:3-4 (1976), 287–304 | DOI | MR | Zbl

[14] E. J. Lemmon, D. Scott, Intensional logics, preliminary draft of initial chapters by E. J. Lemmon, Stanford Univ., 1966; nowadays available as: An introduction to modal logic, American Philosophical Quarterly, Monograph Series, 11, Basil Blackwell, Oxford, 1977, x+94 pp. | MR | Zbl

[15] K. Segerberg, “Decidability of four modal logics”, Theoria, 34 (1968), 21–25 | DOI | MR

[16] D. M. Gabbay, “A general filtration method for modal logics”, J. Philos. Logic, 1:1 (1972), 29–34 | DOI | MR | Zbl

[17] A. Chagrov, M. Zakharyaschev, Modal logic, Oxford Logic Guides, 35, Oxford Univ. Press, New York, 1997, xvi+605 pp. | MR | Zbl

[18] F. Wolter, M. Zakharyaschev, “Modal decision problems”, Handbook of modal logic, Stud. Log. Pract. Reason., 3, Elsevier, Amsterdam, 2007, 427–489 | DOI

[19] V. B. Shehtman, “Filtration via bisimulation”, Advances in modal logic, v. 5, King's Coll. Publ., London, 2005, 289–308 | MR | Zbl

[20] K. Segerberg, “Franzen's proof of Bull's theorem”, Ajatus, 35 (1973), 216–221 | Zbl

[21] K. Segerberg, An essay in classical modal logic, v. 1, 2, 3, Filosofska Studier, 13, Uppsala Univ., Uppsala, 1971, v+250 pp. | MR | Zbl

[22] L. L. Maksimova, “Finite-level modal logics”, Algebra and Logic, 14 (1975), 188–197 | DOI | MR | Zbl

[23] R. Jansana, “Some logics related to von {W}right's logic of place”, Notre Dame J. Formal Logic, 35:1 (1994), 88–98 | DOI | MR | Zbl

[24] A. Kudinov, I. Shapirovsky, “Finite model property of pretransitive analogs of {S5}”, Topology, algebra and categories in logic (TACL 2011), Marseille, 2011, 261–264

[25] P. Blackburn, M. de Rijke, Y. Venema, Modal logic, Cambridge Tracts Theoret. Comput. Sci., 53, Cambridge Univ. Press, Cambridge, 2001, xxii+554 pp. | DOI | MR | Zbl

[26] K. Matsumoto, “Reduction theorem in {L}ewis' sentential calculi”, Math. Japon., 3 (1955), 133–135 | MR | Zbl

[27] D. M. Gabbay, V. B. Shehtman, D. P. Skvortsov, Quantification in nonclassical logic, v. 1, Stud. Logic Found. Math., 153, Elsevier B. V., Amsterdam, 2009, xxiv+615 pp. | MR | Zbl

[28] S. Kikot, I. Shapirovsky, E. Zolin, “Filtration safe operations on frames”, Advances in modal logic, v. 10, King's Coll. Publ., London, 2014, 333–352 | MR

[29] Y. Miyazaki, “Normal modal logics containing KTB with some finiteness conditions”, Advances in modal logic, v. 5, King's Coll. Publ., London, 2005, 171–190 | MR | Zbl

[30] Z. Kostrzycka, “On non-compact logics in NEXT(KTB)”, MLQ Math. Log. Q., 54:6 (2008), 617–624 | DOI | MR | Zbl