Library-Grade Modal Logic
Marianna Girlando, Fabrizio Montesi
cs.LO
Oct 3, 2026 · v1
TL;DR
Builds a generic polyadic modal logic library in Lean within CSLib, reusing Mathlib's PFunctor, and derives several modal logics plus applications.
Abstract
Modal logic comprises a broad family of logics to reason about relational structures. The literature presents many such logics, displaying diverse operators, semantics, and applications. This plurality is reflected in a zoo of mechanised modal logics, which often duplicate syntax, semantics, metatheory, and reasoning infrastructure. We present a library-grade formalisation of modal logic in Lean, developed as part of CSLib (the Lean Computer Science Library) and designed around two complementary forms of reuse: vertical reuse, whereby specialised logics inherit from common abstractions, and horizontal reuse, whereby modal logic becomes a reasoning tool for independently formalised domains. Our development provides a generic framework for polyadic modal languages, reusable metatheory and proof automation, and derived interfaces for specialised modal logics. We exemplify our infrastructure by deriving basic modal logic, basic temporal logic, and Hennessy-Milner Logic; the latter subsumes and extends CSLib's previous implementation while reducing its logic-specific code by 67%. We further apply the same modal infrastructure to reasoning about mathematics (radicals of ideals), theory of programming languages (the type safety strategy for the simply typed $λ$-calculus), and concurrency theory (reasoning about processes in the Calculus of Communicating Systems). Our experience suggests that reuse, automation, and integration with the strong Lean ecosystem should be treated as first-class design concerns when formalising theories for shared libraries.
Problem
Mechanised modal logics are typically developed independently, so each one duplicates its syntax, semantics, metatheory and reasoning infrastructure. CSLib, the Lean computer science library, needed a reusable foundation for modal logic instead of ad-hoc developments.
Approach
Modal similarity types are generalised to Mathlib polynomial functors, allowing operators of arbitrary, possibly infinite arity. On top of this sits a generic framework for polyadic modal languages, frames and satisfaction. The framework provides reusable metatheory, including axioms, frame-condition correspondences and logical equivalence, along with proof automation. Derived interfaces cover unary and unimodal logics and Lean predicates and containers. These support vertical reuse, where specialised logics inherit the generic machinery, and horizontal reuse, where modal logic serves as a tool for other formalised domains.
Results
Basic modal logic, basic temporal logic and Hennessy–Milner Logic are derived from the framework, cutting HML's logic-specific code by 67% and basic modal logic's by 39%. The infrastructure is also applied to radicals of ideals, type safety of the simply typed λ-calculus, and CCS processes.
| Metric | HML Before | HML After | HML Red. (%) | BML Before | BML After | BML Red. (%) |
|---|
| Lines of code | 686 | 224 | 67.3 | 980 | 596 | 39.2 |
| Theorems/lemmas | 43 | 12 | 72.1 | 69 | 39 | 43.5 |
| Definitions | 14 | 1 | 92.9 | 28 | 19 | 32.1 |
| Instances | 19 | 0 | 100.0 | 19 | 6 | 68.4 |
Code reduction after refactoring onto the generic framework