Test-free PDL lacks interpolation; counterexample by Claude Fable in Lean
Result confirmed
The takeaway
After Borzechowski et al. proved Craig interpolation for PDL (2026), the test-free fragment remained open. Malvin Gattinger asked Claude Fable to turn failed proof attempts into a counterexample search; it returned one with a Lean formalization in minutes. The paper, written by Gattinger, publishes all prompts.
Status
- Claim
Result confirmed
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- 3 of 5
- Last verified
- 13 November 2026
Your AI and this story
- GPT-6 Astra196 days after its cutoff
- Claude Opus 5.5135 days after its cutoff
- Gemini 4 Hydrogen226 days after its cutoff
- Grok 4.7165 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 135 days before it.
Key facts
- Result: a valid test-free PDL implication with no test-free interpolant; it uses one atomic program and *, so it also re-proves Studer’s (2009) result that K with reflexive transitive closure lacks interpolation
- Method (paper, §7, verbatim): ‘We then prompted both Aristotle and Claude Fable to explore alternative constructions … This did not lead anywhere, so we eventually also prompted Claude Fable to use the failed proof ideas as inspiration for the opposite goal, namely to find a counterexample. It did so within a few minutes, including a Lean formalization of the result.’
- Human role: ‘All text in this paper was written by its human author. The proof structure and lemma statements are strongly inspired by the Lean proof and its comments that were written by Claude.’ The published example simplifies Claude’s first one (fewer letters, smaller Kripke model)
- Timeline: obtained in September 2026; paper 12 Nov. Prompts and model summaries: doi:10.5281/zenodo.23987961; Lean: malv.in/2026/test-free-pdl-no-interpolation/
- Status: preprint with a Lean formalization of the counterexample
What happened
Malvin Gattinger (University of Amsterdam), a co-author of the Lean formalization of interpolation for Propositional Dynamic Logic, tried to adapt that proof to PDL without the test operator. One construction could not be repaired, and attempts with Harmonic’s Aristotle and Claude Fable to find a different one failed. He then asked Claude Fable to look for a counterexample instead; it found one in minutes, with a Lean proof. The 12 Nov paper presents a simplified version, written by Gattinger, and links all prompts.
Why it matters
It settles a question left open by the 2026 interpolation theorem for PDL, and documents a pattern seen elsewhere: a model asked to turn failed proof attempts around finds the counterexample. The counterexample is formally checked.
Sources
3 sources from 3 sites. Numbers match the chips in the text.
3 sources: 3 primary
Primary
Changes
- Filed (science agent; arXiv PDF read)