Strong Completeness and Limited Canonicity for PDL


Propositional dynamic logic is complete but not compact. As a consequence, strong completeness requires an infinitary proof system. In this paper, we present a short proof for strong completeness of $$\mathsf{PDL}$$ relative to an infinitary proof system containing the rule from [α; β n ]φ for all $$n \in {\mathbb{N}}$$, conclude $$[\alpha;\beta^*] \varphi$$. The proof uses a universal canonical model, and it is generalized to other modal logics with infinitary proof rules, such as epistemic knowledge with common knowledge. Also, we show that the universal canonical model of $$\mathsf{PDL}$$ lacks the property of modal harmony, the analogue of the Truth lemma for modal operators.

Download options


    Upload a copy of this work     Papers currently archived: 72,743

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

64 (#182,459)

6 months
1 (#387,390)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

Dynamic Logic.Lenore D. Zuck & David Harel - 1989 - Journal of Symbolic Logic 54 (4):1480.
Mathematics of Modality.Robert Goldblatt - 1993 - Center for the Study of Language and Information Publications.
Axiomatising the Logic of Computer Programming.Robert Goldblatt - 1985 - Journal of Symbolic Logic 50 (3):854-855.

View all 9 references / Add more references

Citations of this work

Strong Completeness and Limited Canonicity for PDL.Gerard Renardel de Lavalette, Barteld Kooi & Rineke Verbrugge - 2009 - Journal of Logic, Language and Information 18 (2):291-292.
Sequential Dynamic Logic.Alexander Bochman & Dov M. Gabbay - 2012 - Journal of Logic, Language and Information 21 (3):279-298.

Add more citations

Similar books and articles

Some Kinds of Modal Completeness.J. F. A. K. Benthem - 1980 - Studia Logica 39 (2-3):125 - 141.
Canonical Naming Systems.Leon Horsten - 2004 - Minds and Machines 15 (2):229-257.
Presuppositional Completeness.Wojciech Buszkowski - 1989 - Studia Logica 48 (1):23 - 34.
Strong Completeness of Lattice-Valued Logic.Mitio Takano - 2002 - Archive for Mathematical Logic 41 (5):497-505.
On the Canonicity of Sahlqvist Identities.Bjarni Jónsson - 1994 - Studia Logica 53 (4):473 - 491.
Reverse Mathematics and Completeness Theorems for Intuitionistic Logic.Takeshi Yamazaki - 2001 - Notre Dame Journal of Formal Logic 42 (3):143-148.
Emergence, Downwards Causation and the Completeness of Physics.David Yates - 2009 - Philosophical Quarterly 59 (234):110-131.