×

zbMATH — the first resource for mathematics

Finite models constructed from canonical formulas. (English) Zbl 1132.03007
Summary: This paper obtains the weak completeness and decidability results for standard systems of modal logic using models built from formulas themselves. This line of work began with K. Fine [Notre Dame J. Formal Logic 16, 229–237 (1975; Zbl 0245.02025)]. There are two ways in which our work advances on that paper: First, the definition of our models is mainly based on the relation D. Kozen and R. Parikh used in their proof of the completeness of PDL [Theor. Comput. Sci. 14, 113–118 (1981; Zbl 0451.03006)]. The point is to develop a general model-construction method based on this definition. We do this and thereby obtain the completeness of most of the standard modal systems, and in addition apply the method to some other systems of interest. None of the results use filtration, but in our final section we explore the connection.

MSC:
03B45 Modal logic (including the logic of norms)
03B25 Decidability of theories and sets of sentences
03C13 Model theory of finite structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barwise, J. and Moss, L. S.: Vicious Circles: On the Mathematics of Non-wellfounded Phenomena, CSLI Lecture Notes Number 60, CSLI Publications, Stanford University, 1996. · Zbl 0865.03002
[2] Barwise, J. and Moss, L. S.: Modal correspondence for models, The Journal of Philosophical Logic 27 (1998), 275–294. · Zbl 0919.03014 · doi:10.1023/A:1004268613379
[3] Blackburn, P., de Rijke, M., and Venema, Y.: Modal Logic. Cambridge Tracts in Theoretical Computer Science, 53. Cambridge University Press, Cambridge, 2001. · Zbl 0988.03006
[4] Fine, K.: Normal forms in modal logic, Notre Dame Journal of Formal Logic 16 (1975), 229–237. · Zbl 0298.02015 · doi:10.1305/ndjfl/1093891703
[5] Ghilardi, S.: An algebraic theory of normal forms, Annals of Pure and Applied Logic 71(3) (1995), 189–245. · Zbl 0815.03010 · doi:10.1016/0168-0072(93)E0084-2
[6] de Jongh, D.: Investigation on the Intuitionistic Propositional Calculus, PhD Thesis, University of Wisconsin, Madison, 1968. · Zbl 0213.01201
[7] Kozen, D. and Parikh, R.: An elementary proof of the completeness of PDL, Theoretical Computer Science (1981), 113–118. · Zbl 0451.03006
[8] Lemmon, E. J. and Scott, D.: An introduction to modal logics, in Krister Segerberg (ed.), American Philosophical Quarterly, Monograph Series, No. 11, Basil Blackwell, Oxford.
[9] Makinson, D.: Review of Fine [4], Mathematical Reviews MR0366622, vol. 51 #2869. · Zbl 1321.00046
[10] Moss, L. S.: Coalgebraic logic, Annals of Pure and Applied Logic 96(1–3) (1999), 277–317 (publishers’ corrections in 99(1–3) (1999), 241–259). · Zbl 0969.03026
[11] Segerberg, K.: Decidability of S4.1. Theoria 34 (1968), 7–20. · doi:10.1111/j.1755-2567.1968.tb00335.x
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.