Skip to main content
Log in

Expressivity of Second Order Propositional Modal Logic

  • Published:
Journal of Philosophical Logic Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barwise, J. (1975): Admissible Sets and Structures, Springer.

  2. van Benthem, J. (1983): Modal Logic and Classical Logic, Bibliopolis.

  3. Blackburn, P. and Marx, M. (2003): Constructive interpolation in hybrid logic, J. Symb. Log. 68(2), 463–480.

    Article  Google Scholar 

  4. Blackburn, P., de Rijke, M. and Venema, Y. (2001): Modal Logic, Cambridge University Press, Cambridge, UK.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. ten Cate, B. (2005): Model Theory for Extended Modal Languages. PhD thesis, University of Amsterdam. ILLC Dissertation Series DS-2005-01.

  7. Feferman, S. (1968): Persistent and invariant formulas for outer extensions, Compos. Math. 20, 29–52.

    Google Scholar 

  8. 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.

    Article  Google Scholar 

  9. Fine, K. (1970): Propositional quantifiers in modal logic, Theoria, 36, 336–346.

    Article  Google Scholar 

  10. Goldblatt, R. (1975): First-order definability in modal logic, J. Symb. Log. 40(1), 35–40.

    Article  Google Scholar 

  11. 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.

  12. Kaminski, M. and Tiomkin, M. (1996): The expressive power of second-order propositional modal logic, Notre Dame J. Form. Log. 37(1), 35–43.

    Article  Google Scholar 

  13. Kremer, P. (1993): Quantifying over propositions in relevance logic: nonaxiomatizability of primary interpretations of ∀p and ∃p, J. Symb. Log. 58(1), 334–349.

    Article  Google Scholar 

  14. Kremer, P. (1997): On the complexity of propositional quantification in intuitionistic logic, J. Symb. Log. 62(2), 529–544.

    Article  Google Scholar 

  15. Lévy, A. (1965): A Hierarchy of Formulas in Set Theory, volume 57 of Memoirs of the American Mathematical Society.

  16. Otto, M. (2004): Modal and guarded characterisation theorems over finite transition systems, Ann. Pure Appl. Logic 130, 173–205.

    Article  Google Scholar 

  17. Rabin, M. (1969): Decidability of second-order theories and automata on infinite trees, Trans. AMS 141, 1–35.

    Article  Google Scholar 

  18. 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.

  19. van Benthem, J. (1975): A note on modal formulas and relational properties, J. Symb. Log. 40(1), 55–58.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Balder ten Cate.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10992-005-9012-9

Key Words

Navigation