Axiomatizability of propositionally quantified modal logics on relational frames. (English) Zbl 07854638
Summary: Propositional modal logic over relational frames is naturally extended with propositional quantifiers by letting them range over arbitrary sets of worlds of the relevant frame. This is also known as second-order propositional modal logic. The propositionally quantified modal logic of a class of relational frames is often not axiomatizable, although there are known exceptions, most notably the case of frames validating the strong modal logic \(\text{S5} \). Here, we develop new general methods with which many of the open questions in this area can be answered. We illustrate the usefulness of these methods by applying them to a range of examples, which provide a detailed picture of which normal modal logics define classes of relational frames whose propositionally quantified modal logic is axiomatizable. We also apply these methods to establish new results in the multimodal case.
MSC:
| 03B16 | Higher-order logic |
| 03B25 | Decidability of theories and sets of sentences |
| 03B45 | Modal logic (including the logic of norms) |
Keywords:
propositional quantifiers; modal logic; second-order propositional modal logic; axiomatizability; decidability; complexityReferences:
| [1] | Aldo Antonelli, G. and Thomason, R. H., Representability in second-order propositional poly-modal logic, this Journal, vol. 67 (2002), pp. 1039-1054. · Zbl 1034.03014 |
| [2] | Belardinelli, F., Van Der Hoek, W., and Kuijer, L. B., Second-order propositional modal logic: Expressiveness and completeness results. Artificial Intelligence, vol. 263 (2018), pp. 3-45. · Zbl 1436.03128 |
| [3] | Van Benthem, J., Modal Logic for Open Minds, CSLI Publications, Stanford, 2010. |
| [4] | Blackburn, P., De Rijke, M., and Venema, Y., Modal Logic, Cambridge Tracts in Theoretical Computer Science, vol. 53, Cambridge University Press, Cambridge, 2001. · Zbl 0988.03006 |
| [5] | Boolos, G., The Logic of Provability, Cambridge University Press, Cambridge, 1985. |
| [6] | Büchi, J. R., On a decision method in restricted second order arithmetic, Logic, Methodology and Philosophy of Science. Proceedings of the 1960 International Congress (Nagel, E., Suppes, P., and Tarski, A., editors), Stanford University Press, Stanford, 1962, pp. 1-11. · Zbl 0147.25103 |
| [7] | Bull, R. A., On modal logics with propositional quantifiers, this Journal, vol. 34 (1969), pp. 257-263. · Zbl 0184.28101 |
| [8] | Ten Cate, B., Expressivity of second order propositional modal logic. Journal of Philosophical Logic, vol. 35 (2006), pp. 209-223. · Zbl 1106.03016 |
| [9] | Chagrov, A. and Zakharyaschev, M., Modal Logic, Oxford Logic Guides, vol. 35, Clarendon Press, Oxford, 1997. · Zbl 0871.03007 |
| [10] | Ding, Y., On the logic of belief and propositional quantification. Journal of Philosophical Logic, vol. 50 (2021), pp. 1143-1198. · Zbl 1534.03024 |
| [11] | Dorr, C. and Goodman, J., Diamonds are forever. Noûs, vol. 54 (2020), pp. 632-665. · Zbl 1494.03017 |
| [12] | Fine, K., Propositional quantifiers in modal logic. Theoria, vol. 36 (1970), pp. 336-346. · Zbl 0302.02005 |
| [13] | Fine, K., The logics containing S4.3. Zeitschrift für mathematische Logik und Gundlagen der Mathematik, vol. 17 (1971), pp. 371-376. · Zbl 0228.02011 |
| [14] | Fritz, P., Modal ontology and generalized quantifiers. Journal of Philosophical Logic, vol. 42 (2013), pp. 643-678. · Zbl 1320.03014 |
| [15] | Fritz, P., Higher-order contingentism, part 3: Expressive limitations. Journal of Philosophical Logic, vol. 47 (2018), pp. 649-671. · Zbl 1436.03131 |
| [16] | Fritz, P., Propositional quantification in bimodal S5. Erkenntnis, vol. 85 (2020), pp. 455-465. · Zbl 1475.03076 |
| [17] | Fritz, P. and Goodman, J., Counting incompossibles. Mind, vol. 126 (2017), pp. 1063-1108. |
| [18] | Garson, J. W., Quantification in modal logic, Handbook of Philosophical Logic, vol. II, first ed. (Gabbay, D. M. and Guenthner, F., editors), D. Reidel, Dordrecht, 1984, pp. 249-307. · Zbl 0875.03050 |
| [19] | Gurevich, Y., Monadic second-order theories, Model-Theoretic Logics (Barwise, J. and Feferman, S., editors), Springer, New York, 1985, pp. 479-506. |
| [20] | Gurevich, Y. and Shelah, S., Interpreting second-order logic in the monadic theory of order, this Journal, vol. 48 (1983), pp. 816-828. · Zbl 0559.03008 |
| [21] | Gurevich, Y. and Shelah, S., Monadic theory of order and topology in ZFC. Annals of Mathematical Logic, vol. 23 (1983), pp. 179-198. · Zbl 0516.03007 |
| [22] | Hodges, W., A Shorter Model Theory, Cambridge University Press, Cambridge, 1997. · Zbl 0873.03036 |
| [23] | Hughes, G. E. and Cresswell, M. J., An Introduction to Modal Logic, Methuen, London, 1968. · Zbl 0205.00503 |
| [24] | Hughes, G. E. and Cresswell, M. J., Omnitemporal logic and converging time. Theoria, vol. 41 (1975), pp. 11-34. · Zbl 0322.02020 |
| [25] | Hughes, G. E. and Cresswell, M. J., A New Introduction to Modal Logic, Routledge, London, 1996. · Zbl 0855.03002 |
| [26] | Kaminski, M. and Tiomkin, M., The expressive power of second-order propositional modal logic. Notre Dame Journal of Formal Logic, vol. 37 (1996), pp. 35-43. · Zbl 0895.03005 |
| [27] | Kaplan, D., S5 with quantifiable propositional variables, this Journal, vol. 35 (1970), p. 355. |
| [28] | Kaplan, D.. Demonstratives, Themes from Kaplan (Almog, J., Perry, J., and Wettstein, H., editors), Oxford University Press, Oxford, 1989 [1977], pp. 481-563. Completed and circulated in mimeograph in the published form in 1977. |
| [29] | Karp, C. R., Finite-quantifier equivalence, The Theory of Models. Proceedings of the 1963 International Symposium at Berkeley (Addison, J. W., Henkin, L., and Tarski, A., editors), North-Holland, Amsterdam, 1965, pp. 407-412. · Zbl 0253.02052 |
| [30] | Kremer, P., Quantifying over propositions in relevance logic: Nonaxiomatisability of primary interpretations of \(\forall p\) and \(\exists p\) , this Journal, vol. 58 (1993), pp. 334-349. · Zbl 0786.03016 |
| [31] | Kremer, P., On the complexity of propositional quantification in intuitionistic logic, this Journal, vol. 62 (1997), pp. 529-544. · Zbl 0887.03002 |
| [32] | Kripke, S. A., A completeness theorem in modal logic, this Journal, vol. 24 (1959), pp. 1-14. · Zbl 0091.00902 |
| [33] | Kripke, S. A., Semantical analysis of modal logic I: Normal modal propositional calculi. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 9 (1963), pp. 67-96. · Zbl 0118.01305 |
| [34] | Kuhn, S., A simple embedding of T into double S5. Notre Dame Journal of Formal Logic, vol. 45 (2004), pp. 13-18. · Zbl 1088.03020 |
| [35] | Kurucz, A., Combining modal logics, Handbook of Modal Logic (Blackburn, P., Van Benthem, J., and Wolter, F., editors), Elsevier, Amsterdam, 2007, pp. 869-924. · Zbl 1114.03001 |
| [36] | Lewis, C. I. and Langford, C. H., Symbolic Logic, second ed., Dover, New York, 1959 [1932]. Republication of the first edition published by The Century Company in 1932. · JFM 58.0056.01 |
| [37] | Löwenheim, L., Über Möglichkeiten im Relativkalkül. Mathematische Annalen, vol. 76 (1915), pp. 447-470. · JFM 45.0108.01 |
| [38] | Makinson, D., Some embedding theorems for modal logic. Notre Dame Journal of Formal Logic, vol. 12 (1971), pp. 252-254. · Zbl 0193.29301 |
| [39] | Montague, R., The proper treatment of quantification in ordinary English, Approaches to Natural Language: Proceedings of the 1970 Stanford Workshop on Grammar and Semantics (Hintikka, J., Moravcsik, J., and Suppes, P., editors), D. Reidel, Dordrecht, 1973, pp. 221-242. |
| [40] | Nagle, M. C. and Thomason, S. K., The extensions of the modal logic K5, this Journal, vol. 50 (1985), pp. 102-109. · Zbl 0586.03012 |
| [41] | Nerode, A. and Shore, R. A., Second order logic and first-order theories of reducibility orderings, The Kleene Symposium (Jon Barwise, H. J. Keisler, and K.Kunen, editors), North-Holland, Amsterdam, 1980, pp. 181-200. · Zbl 0465.03024 |
| [42] | Parry, W. T., Zum Lewisschen Aussagenkalkül. Ergebnisse eines Mathematischen Kolloquiums, vol. 4 (1933), pp. 15-16. · JFM 59.0863.01 |
| [43] | Prior, A. N., Time and Modality, Clarendon Press, Oxford, 1957. · Zbl 0079.00606 |
| [44] | Prior, A. N., On a family of paradoxes. Notre Dame Journal of Formal Logic, vol. 2 (1961), pp. 16-32. · Zbl 0112.00408 |
| [45] | Prior, A. N., Past, Present and Future, Clarendon Press, Oxford, 1967. · Zbl 0169.29802 |
| [46] | Prior, A. N., Egocentric logic. Noûs, vol. 2 (1968), pp. 191-207. |
| [47] | Prior, A. N., Objects of Thought, Clarendon Press, Oxford, 1971. Edited by P. T. Geach and A. J. P. Kenny. |
| [48] | Rabin, M. O., Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1-35. · Zbl 0221.02031 |
| [49] | Reynolds, M. and Zakharyaschev, M., On the products of linear modal logics. Journal of Logic and Computation, vol. 11 (2001), pp. 909-931. · Zbl 1002.03017 |
| [50] | Scott, D., Advice on modal logic, Philosophical Problems in Logic. Some Recent Developments (Lambert, K., editor), D. Reidel, Dordrecht, 1970, pp. 143-173. · Zbl 0295.02013 |
| [51] | Segerberg, K., Modal logics with linear alternative relations. Theoria, vol. 36 (1970), pp. 301-322. · Zbl 0235.02019 |
| [52] | Segerberg, K., A note on the logic of elsewhere. Theoria, vol. 46 (1980), pp. 183-187. |
| [53] | Shapiro, S., Foundations without Foundationalism: A Case for Second-Order Logic, Clarendon Press, Oxford, 1991. · Zbl 0732.03002 |
| [54] | Shelah, S., The monadic theory of order. Annals of Mathematics, vol. 102 (1975), pp. 379-419. · Zbl 0345.02034 |
| [55] | Sobociński, B., Remarks about axiomatizations of certain modal systems. Notre Dame Journal of Formal Logic, vol. 5 (1964), pp. 71-80. · Zbl 0137.00504 |
| [56] | Väänänen, J., Second-order and higher-order logic, The Stanford Encyclopedia of Philosophy (Zalta, E. N., editor), Metaphysics Research Lab, Stanford University, Stanford, 2019. |
| [57] | Von Wright, G. H., A modal logic of place, The Philosophy of Nicholas Rescher: Discussion and Replies (Sosa, E., editor), D. Reidel, Dordrecht, 1979, pp. 65-73. |
| [58] | Zach, R., Decidability of quantified propositional intuitionistic logic and S4 on trees of height and arity \(\le \omega \). Journal of Philosophical Logic, vol. 33 (2004), pp. 155-164. · Zbl 1054.03011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
