💻 computer science

Formalizing a Many-Sorted Hybrid Polyadic Modal Logic in Lean

This paper presents a machine-checked Lean formalization of a general many-sorted hybrid polyadic modal logic with an intrinsic sorting mechanism and a domain-specific language, providing a sound and versatile framework for specifying and verifying programming languages and security protocols.

Original authors: Andrei-Alexandru Oltean, Bogdan Macovei, Ioana Leuştean

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrei-Alexandru Oltean, Bogdan Macovei, Ioana Leuştean

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an architect trying to build a universal "logic toolbox" that can be used to check if computer programs work correctly, if secret messages in security protocols are safe, or if philosophical arguments hold water. The problem is that every job requires a slightly different set of tools, and usually, you have to build a new toolbox from scratch for each one.

This paper presents a solution: a universal, machine-checked logic toolbox built inside a software program called Lean. The authors have created a system that is flexible enough to handle complex, multi-layered rules (many-sorted) and can look at different "states" or "worlds" (hybrid logic) all at once.

Here is a breakdown of their work using everyday analogies:

1. The "List Trick": Building with LEGO Bricks

The biggest challenge in this project was making sure that the rules of the logic were followed automatically, without needing a human to double-check every single step.

The Problem: In traditional logic, you might write a formula and then have to run a separate "spell-checker" to see if it makes sense (e.g., "Did you try to add a number to a sentence?").
The Solution (The List Trick): The authors treated logical formulas like lists of LEGO bricks. They designed the system so that you physically cannot snap two incompatible bricks together. If you try to connect a "red" brick (a specific type of rule) to a "blue" brick (a different type), the system simply won't let you click them together.
Why it matters: This means that if a formula exists in their system, it is guaranteed to be correct by definition. They don't need to check for errors later because the structure itself prevents errors from happening in the first place.

2. The "Context" Pointer: Finding a Needle in a Haystack

The logic they built allows for complex operations where you might need to change a specific part of a long, complicated sentence.

The Analogy: Imagine you have a long paragraph of text, and you want to replace the word "cat" with "dog." In a normal document, you might just search and replace. But in their system, there might be many "cats," and you need to change only the one in the second sentence, not the one in the fifth.
The Solution: They created a digital "pointer" (called a Context). This pointer is like a GPS coordinate that says, "I am pointing specifically to the 'cat' in the second sentence." When they apply a rule, they use this pointer to swap out exactly that specific word, leaving everything else untouched. This allows them to handle very complex, multi-part rules without getting confused.

3. The DSL: A "Language Translator"

To make this powerful system usable for regular people (like programmers or security experts), the authors built a Domain-Specific Language (DSL).

The Analogy: Think of the core logic as a high-level programming language (like C++ or Assembly) that is very powerful but hard to read. The DSL is like a translator that lets users write in a friendly, familiar style (like a recipe or a flowchart).
How it works: A user can write a rule that looks like a standard computer program (e.g., "If X, then do Y"). The system automatically translates this into the complex, underlying logic bricks. This means users don't need to be logicians to use the system; they just need to know their specific field (like coding or security).

4. Three Real-World Tests

To prove their toolbox works, they used it to solve three very different problems:

The Program Checker (SMC Machine): They used the system to verify a simple computer program. They translated the program's steps into their logic and proved that if you start with specific numbers, the program will definitely end with the correct result. It's like proving a math equation is true before you even run the calculator.
The Security Protocol Detective (BAN Logic): They modeled how two people exchange secret keys over a network. They used the logic to prove that if a message is encrypted with a specific key, the receiver can be 100% sure who sent it. They successfully verified a famous security protocol (Needham-Schroeder) to show the system can catch potential security flaws.
The Philosophical Simplifier (S5 Logic): They showed that their complex system can also handle simple, standard logic (S5). This proves the system is versatile enough to be a "Swiss Army Knife"—it can handle the most complex multi-world scenarios, but it can also shrink down to handle simple, everyday logic if needed.

5. The "Soundness" Guarantee

The most important claim of the paper is Soundness.

The Analogy: Imagine a judge in a court. The judge needs to be sure that if they say "Guilty," the person actually committed the crime according to the law.
The Result: The authors used the Lean software to mathematically prove that their system is sound. This means: If the system says a statement is true, it is mathematically impossible for it to be false. They didn't just guess; they built a machine-checked proof that their rules never lead to a lie.

Summary

In short, the authors built a super-flexible, error-proof logic engine inside a computer program. They created a way for users to define their own rules easily, translated those rules into a format that the computer can verify with 100% certainty, and proved that the engine works correctly for everything from checking code to securing digital messages. It's a universal translator that turns human ideas into mathematically guaranteed truths.

Technical Summary: Formalizing a Many-Sorted Hybrid Polyadic Modal Logic in Lean

Problem Statement

The paper addresses the challenge of providing a uniform, mathematically sound axiomatic foundation for specifying and verifying diverse systems, such as programming languages and security protocols. Existing formalizations often lack the flexibility to handle many-sorted signatures (where different types of entities exist) and polyadic modal operators (operators with arbitrary arities) within a single framework. Furthermore, while hybrid modal logics (which include nominals and state variables) are powerful for referencing specific states, their formalization in proof assistants has traditionally been limited to mono-sorted or monadic settings. The authors aim to bridge this gap by creating a general framework in the Lean proof assistant that supports arbitrary signatures, polyadic operators, and hybrid features, while ensuring that the syntax is intrinsically well-sorted to prevent type errors during verification.

Methodology

The authors implement a formalization of the general hybrid modal logic $H_\Sigma(@, \forall)$ within Lean's dependent type theory. Their methodology relies on three core technical innovations:

1. Intrinsic Sorting via the "List Trick"

To avoid the need for separate "sort-checking" functions, the authors utilize Lean's dependent types to enforce sorting constraints at the type level.

Inductive Types: Formulas are represented by an inductive type FormL indexed by a List of sorts.
The List Trick: While standard formulas correspond to singleton lists of sorts, the authors introduce an artificial constructor cons that allows building lists of formulas indexed by non-singleton lists of sorts.
Mechanism: Modal operators are defined to take a list of arguments (the domain sorts) and return a formula of a specific range sort. The type checker verifies that the list of argument sorts matches the operator's domain signature exactly. This ensures that any constructed term is a well-sorted formula by definition.
Contexts: To handle polyadic operators and axioms involving generic arguments (e.g., substitution within an arbitrary argument slot of an operator), the authors define an inductive type Context. A Context acts as a pointer to a specific occurrence of a sub-formula within a list of formulas, enabling rigorous substitution without relying on informal "..." notation.

2. Semantic Formalization

The semantics are defined using Kripke frames and models that are also many-sorted.

Worlds: A frame maps each sort to a type in a universe.
Accessibility Relations: Relations are defined as sets of WProd (a product type constructed from the list of sorts), representing tuples of worlds that satisfy the relation.
Satisfaction: The satisfaction relation is defined recursively. The list trick simplifies the handling of polyadic operators: the satisfaction of a list of arguments is defined as the simultaneous satisfaction of the list at a product of worlds.

3. Axiomatic Extensions and Proof System

The proof system is parametric over an axiomatic extension $\Lambda$ .

Axiom Sets: Axioms are defined as S-sorted sets of formulas.
Inductive Proofs: The Proof type is an inductive family. Crucially, the authors use inductive types to define axiom schemas. Instead of manually listing infinite instances, they define an inductive family of axioms (e.g., for the SMC machine or BAN logic) where constructors represent schema patterns. The set of theorems is then the closure of these schemas under deduction rules.
Soundness: The authors prove the Frame-Soundness Theorem: if a formula is provable from a set of axioms $\Lambda$ , it is valid in all frames where $\Lambda$ is valid.

Key Contributions and Results

General Formalization: The paper presents the first machine-checked formalization of a general many-sorted hybrid polyadic modal logic in Lean. This system supports arbitrary signatures, polyadic operators, and hybrid features (nominals, satisfaction operators $@$ , and binders $\forall$ ).
Mechanized Soundness: A complete, "sorry-free" proof of the soundness theorem is provided. During this process, the authors identified and corrected errors in the original presentation of the proof system found in prior literature (specifically regarding the Barcan axiom and the Name@ and Paste rules), providing a corrected version with necessary syntactic side-conditions.
DSL for Signature Definition: The authors developed a Domain Specific Language (DSL) using the hybrid_def keyword. This allows users to define many-sorted signatures using familiar Backus-Naur Form (BNF)-like notation, which is automatically elaborated into the underlying Lean data structures (Symbols, Signature, etc.).
Three Verified Applications: The framework's versatility is demonstrated through three distinct applications:
- SMC Machine (Program Analysis): The authors formalized the operational semantics of the SMC machine (an imperative language) as a hybrid logic signature. They derived Hoare-like inference rules and verified the correctness of a program involving variable swapping and conditional execution with side effects.
- Security Protocols: The framework was used to embed BAN Logic and a hybrid logic for security protocols. They verified authentication properties in the Needham-Schroeder Public Key (NSPK) protocol and analyzed the One-Sided Secrecy (OSS) protocol, proving mutual authentication and knowledge properties.
- S5 Modal Logic: The authors demonstrated that the system can restrict itself to a purely modal fragment (removing hybrid features) to define and prove theorems in the S5 modal system, showing the framework's ability to handle less expressive fragments of the base logic.

Significance and Claims

The paper claims that the proposed system serves as a general verification framework capable of unifying the specification of programming languages, their operational semantics, and correctness properties within a single logical foundation.

Modularity and Extensibility: The authors emphasize that the architecture is modular. Users can define custom languages or protocols as many-sorted signatures and specify domain-specific axioms without altering the core logic.
Intrinsic Safety: By using intrinsic sorting, the framework guarantees that any formula constructed is a valid parse of the defined grammar, eliminating a class of errors common in other formalizations.
Research Tool: The representation of variables as concrete names (rather than de Bruijn indices) is a deliberate choice to facilitate the migration of pen-and-paper logic research into the formal setting, minimizing representational overhead.

The work positions itself as a rigorous foundation for future extensions, specifically noting that the Completeness Theorem remains a target for future mechanization, and that the development of user-friendly tactics is a priority to make the system accessible to non-experts in the implementation details. The code is openly available, supporting reproducibility and further development in the field of formal methods.