Abstract
We consider second-order propositional modal logic (SOPML), an extension of the basic modal language with propositional quantifiers introduced by Kit Fine in 1970. We determine the precise expressive power of SOPML by giving analogues of the Van Benthem–Rosen theorem and the Goldblatt Thomason theorem. Furthermore, we show that the basic modal language is the bisimulation invariant fragment of SOPML, and we characterize the bounded fragment of first-order logic as being the intersection of first-order logic and SOPML.
Similar content being viewed by others
References
Barwise, J. (1975): Admissible Sets and Structures, Springer.
van Benthem, J. (1983): Modal Logic and Classical Logic, Bibliopolis.
Blackburn, P. and Marx, M. (2003): Constructive interpolation in hybrid logic, J. Symb. Log. 68(2), 463–480.
Blackburn, P., de Rijke, M. and Venema, Y. (2001): Modal Logic, Cambridge University Press, Cambridge, UK.
Buss, S. R. (1997): Bounded arithmetic and propositional proof complexity, in H. Schwichtenberg (ed.), Logic and Computation, Springer, Berlin Heidelberg New York, pp. 67–122.
ten Cate, B. (2005): Model Theory for Extended Modal Languages. PhD thesis, University of Amsterdam. ILLC Dissertation Series DS-2005-01.
Feferman, S. (1968): Persistent and invariant formulas for outer extensions, Compos. Math. 20, 29–52.
Feferman, S. and Kreisel, G. (1966): Persistent and invariant formulas relative to theories of higher order, Bull. Am. Math. Soc. 72, 480–485. Research Announcement.
Fine, K. (1970): Propositional quantifiers in modal logic, Theoria, 36, 336–346.
Goldblatt, R. (1975): First-order definability in modal logic, J. Symb. Log. 40(1), 35–40.
Janin, D. and Walukiewicz, I. (1996): On the expressive completeness of the propositional mu-calculus with respect to monadic second-order logic, in U. Montanari and V. Sassone (eds.), Proceedings of the seventh International Conference on Concurrency Theory (CONCUR'96), volume 1119 of Lecture Notes in Computer Science, Springer, pp. 263–277.
Kaminski, M. and Tiomkin, M. (1996): The expressive power of second-order propositional modal logic, Notre Dame J. Form. Log. 37(1), 35–43.
Kremer, P. (1993): Quantifying over propositions in relevance logic: nonaxiomatizability of primary interpretations of ∀p and ∃p, J. Symb. Log. 58(1), 334–349.
Kremer, P. (1997): On the complexity of propositional quantification in intuitionistic logic, J. Symb. Log. 62(2), 529–544.
Lévy, A. (1965): A Hierarchy of Formulas in Set Theory, volume 57 of Memoirs of the American Mathematical Society.
Otto, M. (2004): Modal and guarded characterisation theorems over finite transition systems, Ann. Pure Appl. Logic 130, 173–205.
Rabin, M. (1969): Decidability of second-order theories and automata on infinite trees, Trans. AMS 141, 1–35.
Stirling, C. (2003): Bisimulation and language equivalence, in Ruy J. G. B. de Queiroz (ed.), Logic for Concurrency and Synchronisation, Trends in Logic, Kluwer Academic, pp. 269–284.
van Benthem, J. (1975): A note on modal formulas and relational properties, J. Symb. Log. 40(1), 55–58.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
ten Cate, B. Expressivity of Second Order Propositional Modal Logic. J Philos Logic 35, 209–223 (2006). https://doi.org/10.1007/s10992-005-9012-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10992-005-9012-9