← All papers
First page of Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof

Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof

Manfred Borzechowski, Malvin Gattinger, Helle Hvid Hansen, Revantha Ramanayake, Francisco Trucco Dalmas, Yde Venema

cs.LO Mar 17, 2025 · v3 math.LO
The Craig interpolation proof for PDL, including soundness, completeness, interpolation and Beth definability, is formally verified in Lean 4 (lean4-pdl repository).
We show that Propositional Dynamic Logic (PDL) has the Craig Interpolation Property. This question has been open for many years. Three proof attempts were published, but later criticized in the literature or retracted. Our proof is based on the main ideas from Borzechowski (1988, master thesis). We define a cyclic tableau system for PDL with a loading mechanism to recognize successful repeats. For this system, we show soundness and completeness via a game. To show interpolation, we modify Maehara's method to work for tableaux with repeats: we first define pre-interpolants at each node, and then use a quasi-tableau to define interpolants for clusters (strongly connected components). In different terms, our method solves the fixpoint equations that characterize the desired interpolants, and the method ensures that the solutions to these equations can be expressed within PDL. The proof is constructive and we show how to compute interpolants. We make available a Haskell implementation of the proof system that provides interpolants, and a formal verification of our proof in the interactive theorem prover Lean. Lastly, we discuss several questions for future work.

Whether Propositional Dynamic Logic (PDL) has the Craig Interpolation Property has been open for many years. Three earlier published proof attempts were criticized or retracted.

The authors define a cyclic tableau system for PDL that uses a loading mechanism to recognize successful repeats, and prove soundness and completeness via a game. They adapt Maehara's method to tableaux with repeats: pre-interpolants are defined at each node, and a quasi-tableau defines interpolants for clusters (strongly connected components), solving the fixpoint equations that characterize interpolants within PDL. The proof is constructive, implemented in Haskell, and formalized in Lean 4.

PDL has the Craig Interpolation Property and, as a consequence, the Beth definability property. The main theorems are fully verified in Lean, and a Haskell tool computes interpolants.