Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T01:41:41.971Z Has data issue: false hasContentIssue false

A new proof of Sahlqvist's theorem on modal definability and completeness

Published online by Cambridge University Press:  12 March 2014

G. Sambin
Affiliation:
Dipartimento di Matematica Pura ed Applicata, Università Degli Studi di Padova, 35131 Padova, Italy
V. Vaccaro
Affiliation:
Dipartimento di Matematica e Applicazioni, Università Degli Studi di Napoli, 80134 Napoli, Italy

Extract

There are not many global results on modal logics. One of these is the following theorem by Sahlqvist on completeness and correspondence for a wide class of modal formulae (including many well known logics, e.g. D, T, B, S4, K4, S5, …) (see [S]).

Sahlqvist's Theorem. Let A be any modal formula which is equivalent to a conjunction of formulae of the form □m(A1 → A2), where m ≥ 0, A2 is positive and A1 is obtained from propositional variables and their negations applying ∧, ∨, ♢, and □ in such a way that no positive occurrence of a variable is in a subformula of the form B1 ∨ B2 or ♢ B1 within the scope of some □. Then A corresponds effectively to a first order formula, and L + A is canonical whenever Lis a canonical logic.

A formula A satisfying the above conditions is henceforth called a Sahlqvist formula. Unfortunately, till now, the only complete proof was the original proof of Sahlqvist (a proof of the correspondence half has also been given by van Benthem [vB]). It is so complicated and long that even in an advanced textbook of modal logic [HC] it has not found a place. Here, by considering general frames as topological spaces, an attitude which we developed in [TD], we give a proof of Sahlqvist's theorem simplified to such an extent that one can easily grasp the key idea on which it is based and apply the resulting algorithm to specific modal formulae in a straightforward manner, suitable even for implementation on a personal computer. This key idea also improves on previous preliminary work in the same direction (see [S1], [S2]).

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[vB]van Benthem, J. F. A. K., Modal logic and classical logic, Bibliopolis, Naples, 1985.Google Scholar
[E]Esakia, L., Topological Kripke models, Soviet Mathematics Doklady, vol. 15 (1974), pp. 147151.Google Scholar
[G]Goldblatt, R. I., Metamathematics of modal logic, Reports on Mathematical Logic, vol. 6 (1976), pp. 4177, and vol. 7 (1977), pp. 21–52.Google Scholar
[HC]Hughes, G. E. and Cresswell, M. J., A companion to modal logic, Methuen, London, 1984.Google Scholar
[S]Sahlqvist, H., Completeness and correspondence in the first and second order semantics for modal logic, Proceedings of the third Scandinavian logic symposium (Kanger, S., editor), North-Holland, Amsterdam, 1975, pp. 110143.CrossRefGoogle Scholar
[S1]Sambin, G., A simpler proof of Sahlqvist's theorem on completeness of modal logics, Polish Academy of Sciences, Institute of Philosophy and Sociology, Bulletin of the Section of Logic, vol. 9 (1980), pp. 5056.Google Scholar
[S2]Sambin, G., Topology and categorical duality in the study of semantics for modal logics, Report No. 104, Fachbereich Mathematik, Freie Universität Berlin, Berlin, 1979.Google Scholar
[TD]Sambin, G. and Vaccaro, V., Topology and duality in modal logic, Annals of Pure and Applied Logic, vol. 37 (1988), pp. 249296.CrossRefGoogle Scholar