Abstract
In this paper, we introduce a variant of second-order propositional modal logic interpreted on general (or Henkin) frames, \(SOPML^{\mathcal {H}}\), and present a decidable fragment of this logic, \(SOPML^{\mathcal {H}}_{dec}\), that preserves important expressive capabilities of \(SOPML^{\mathcal {H}}\). \(SOPML^{\mathcal {H}}_{dec}\) is defined as a modal loosely guarded fragment of \(SOPML^{\mathcal {H}}\). We demonstrate the expressive power of \(SOPML^{\mathcal {H}}_{dec}\) using examples in which modal operators obtain (a) the epistemic interpretation, (b) the dynamic interpretation. \(SOPML^{\mathcal {H}}_{dec}\) partially satisfies the principle of non-Fregean logic: two different atomic propositions with the same truth value can have different contents. In \(SOPML^{\mathcal {H}}_{dec}\), we also define relating connectives and show that the weak Boethius’ Thesis built using these connectives is a valid formula of \(SOPML^{\mathcal {H}}_{dec}\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
For the precise expressive power of \(SOPML^{full}\), see ten Cate (2006).
Non-Fregean logics were introduced by Suszko (1971). Nowadays, interest in these logics has been renewed ( Shramko and Wansing (2009); Lewitzka (2011); Golińska-Pilarek and Huuskonen (2016)). Let us also pay attention to other studies, which note that classical semantics (based on truth values of propositions) is often insufficient. We mean the branch of non-classical logic that explores hyperintensional contexts and operators (see, e.g., Cresswell (1975); Leitgeb (2019)).
The standard translation of modal logic into first-order and monadic second-order logic is defined, in particular, in Blackburn et al. (2001, Sections 2.4 and 3.2) . Note that \(MSO^{\mathcal {H}}\) can be considered as a first-order many-sorted logic; and this many-sorted logic in turn can be converted into a one-sorted logic (we will cover this in more detail in Sect. 3). Hence we could define a direct translation of \(SOPML^{\mathcal {H}}\) into first-order logic. But such a translation seems less visual and convenient.
In this connection, note that we are not aware of works on \(SOPML\) where the mentioned predicate symbols are used.
Super predicate symbols are predicate symbols that take as arguments both individual variables and predicate variables (see Enderton (2009, Section 4)).
Some (more general) version of this statement is proved in van Benthem and Doets (2001, Section 4.2)).
Besides (as was mentioned in Sect. 2.2), \(\varepsilon \) allows us to distinguish truth values and contents of atomic propositions.
We believe that this atomic formulas can be expressed in \(SOPML\) interpreted on full frames and cannot be expressed in \(SOPML\) on general frames. But a proof of this fact is required.
Note that besides free predicate variables of \(ST_y(\psi )\), G also contains the free individual variable y of \(ST_y(\psi )\).
We regard (EX) as an ambiguous sentence (having different readings) similar to Quine’s famous sentence ‘Ralph believes (knows) that someone is a spy’.
Let some formula of LGF\(_\Box \) contain sequentially a modal operator (say \(K_d\)) and existential quantifier (say \(\exists p\)). See, for example, the formula (3). It can easily be checked that the class of formulas LGF\(_\Box \) is not closed on permuting \(K_d\) and \(\exists p\). Some guard appears between \(\exists p\) and \(K_d\) after permutation. See the formula (4).
In this paper, we do not consider formulas with nested relating connectives.
In a more general form, this statement is presented in (van Benthem and Doets (2001, Section 4.2)).
References
Andréka, H., Németi, I., & van Benthem, J. (1998). Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27(3), 217–274. https://doi.org/10.1023/A:1004275029985
Antonelli, G. A., & Thomason, R. H. (2002). Representability in second-order propositional poly-modal logic. The Journal of Symbolic Logic, 67(3), 1039–1054. https://doi.org/10.2178/jsl/1190150147
Belardinelli, F., van der Hoek, W., & Kuijer, L. B. (2018). Second-order propositional modal logic: expressiveness and completeness results. Artificial Intelligence, 263, 3–45. https://doi.org/10.1016/j.artint.2018.07.004
Blackburn, P., de Rijke, M., & Venema, Y. (2001). Modal Logic, Vol. 53. In Cambridge tracts in theoretical computer science. Cambridge: Cambridge University Press https://doi.org/10.1017/CBO9781107050884
Cresswell, M. J. (1975). Hyperintensional Logic. Studia Logica, 34(1), 25–38. https://doi.org/10.1007/bf02314421
Degtyarev, A., & Voronkov, A. (2001). The inverse method. In A. Robinson & A. Voronkov (Eds.), Handbook of automated reasoning (Vol. 1, pp. 179–272). Amsterdam: Elsevier Science Publishers B.V.
Enderton, H.B. (2009) Second-order and higher-order logic. Stanford Encyclopedia of Philosophy. https://plato.stanford.edu/archives/sum2019/entries/logic-higher-order/.
Golińska-Pilarek, J., & Huuskonen, T. (2016). Non-Fregean propositional logic with quantifiers. Notre Dame Journal of Formal Logic, 57(2), 249–279. https://doi.org/10.1215/00294527-3470547
Grädel, E. (1999). On the restraining power of guards. The Journal of Symbolic Logic, 64(4), 1719–1742. https://doi.org/10.2307/2586808
Harel, D., Kozen, D., & Tiuryn, J. (2000). Dynamic logic. Cambridge: The MIT Press.
Hodkinson, I. (2002). Loosely guarded fragment of first-order logic has the finite model property. Studia Logica, 70(2), 205–240. https://doi.org/10.1023/A:1015178417181
Jarmużek, T., & Klonowski, M. (2020). Introduction to relating logic. Beijing: Beijing Normal University.
Jarmużek, T., & Malinowski, J. (2019). Boolean connexive logics: Semantics and tableau approach. Logic and Logical Philosophy, 28(3), 427-448. https://doi.org/10.12775/LLP.2019.003
Kaminski, M., & Tiomkin, M. L. (1996). The expressive power of second-order propositional modal logic. Notre Dame Journal of Formal Logic, 37(1), 35–43. https://doi.org/10.1305/ndjfl/1040067314
Kerber, M. (1991) How to prove higher order theorems in first order logic. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), (pp. 137–142).
Kokorin, A. I., & Pinus, A. G. (1978). Decidability problems of extended theories. Russian Mathematical Surveys, 33(2), 53–96.
Leitgeb, H. (2019). HYPE: A system of hyperintensional logic (with an application to semantic paradoxes). Journal of Philosophical Logic, 48(2), 305–405. https://doi.org/10.1007/s10992-018-9467-0
Lespérance, Y., & Levesque, H. J. (1995). Indexical knowledge and robot action - A logical account. Artificial Intelligence, 73(1–2), 69–115. https://doi.org/10.1016/0004-3702(94)00010-X
Lespérance, Y., Levesque, H. J., Lin, F., & Scherl, R. B. (2000). Ability and knowing how in the situation calculus. Studia Logica, 66(1), 165–186. https://doi.org/10.1023/A:1026761331498
Lewitzka, S. (2011). \(\in _K\): a Non-Fregean logic of explicit knowledge. Studia Logica, 97(2), 233–264. https://doi.org/10.1007/s11225-011-9304-8
Marx, M. (2001). Tolerance logic. Journal of Logic, Language and Information, 10, 353–374. https://doi.org/10.1023/A:1011207512025
Shapiro, S. (1991). Foundations without foundationalism. A case for second-order logic. Oxford: Oxford University Press.
Shramko, Y., & Wansing, H. (2009). The slingshot argument and sentential identity. Studia Logica, 91(3), 429–455. https://doi.org/10.1007/s11225-009-9182-5
Shtakser, G. (2018). Propositional epistemic logics with quantification over agents of knowledge. Studia Logica, 106(2), 311–344. https://doi.org/10.1007/s11225-017-9741-0
Shtakser, G. (2019). Propositional epistemic logics with quantification over agents of knowledge (An alternative approach). Studia Logica, 107(4), 753–780. https://doi.org/10.1007/s11225-018-9824-6
Suszko, R. (1971). Identity connective and modality. Studia Logica, 27, 7–41.
ten Cate, B. (2006). Expressivity of second-order propositional modal logic. Journal of Philosophical Logic, 35(2), 209–223. https://doi.org/10.1007/s10992-005-9012-9
van Benthem, J. (1997). Dynamic bits and pieces. Technical Report LP-97-01. Institute for Logic, Language and Computation, University of Amsterdam.
van Benthem, J., & Doets, K. (2001). Higher-order logic. In D. M. Gabbay & F. Guenthner (Eds.), Handbook of philosophical logic (2nd ed., Vol. 1, pp. 189–244). Amsterdam: Kluwer Academic Publisher.
Wansing, H. (2020) Connexive logic. Stanford encyclopedia of philosophy.
Acknowledgements
I would like to express my appreciation for the time and effort of the referee, whose comments allowed me to make the paper much more clear and transparent.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Shtakser, G. A Modal Loosely Guarded Fragment of Second-Order Propositional Modal Logic. J of Log Lang and Inf 32, 511–538 (2023). https://doi.org/10.1007/s10849-022-09390-x
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10849-022-09390-x