🤖 AI

First-Order Modal Logic in HOL: Deep and Shallow Embeddings with Automated Faithfulness (Extended Preprint)

This paper extends the deep-and-shallow embedding methodology from propositional to first-order modal logic within Isabelle/HOL by providing three distinct embeddings, developing necessary substitution machinery for quantifiers, and mechanizing the downward Löwenheim-Skolem theorem to automate a global faithfulness proof that reconciles deep validity with minimal-shallow interpretations over full domains.

Original authors: Christoph Benzmüller, Daniel Kirchner

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Christoph Benzmüller, Daniel Kirchner

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 trying to teach a super-smart robot (let's call it "Isabelle") how to think about a universe where things can be true in some places but false in others, and where you can talk about "everyone" or "someone" in those places. This is the world of First-Order Modal Logic (FML). It's like a game of "What if?" mixed with a roll call of every possible person.

The problem is that Isabelle speaks a very precise, high-level language called Higher-Order Logic (HOL). To get Isabelle to understand our "What if?" game, the authors had to build three different bridges (embeddings) to translate our logic into Isabelle's language.

The Three Bridges

The Deep Bridge (The Blueprint): This is like building a literal, physical model of the logic using Lego bricks. Every single rule, every "and," every "not," and every "for all" is a distinct brick in a giant structure. It's heavy and detailed, perfect for studying the shape of the logic itself, but it's hard for the robot to run fast on it.
The Heavyweight Shallow Bridge (The Full-Service Hotel): This bridge is like a luxury hotel where every guest (every formula) gets their own room, and the room comes with its own map of the world, a list of all possible people, and a specific guide. It carries everything explicitly. It's very clear, but it's a bit bulky to carry around.
The Lightweight Shallow Bridge (The Minimalist Tent): This is the paper's star player. It's a tiny, portable tent. Instead of carrying a full map and a list of everyone, it just carries a "world" and a "guide." It assumes the rest of the furniture is already there. It's so light that the robot can run its automatic reasoning tools (like "Sledgehammer" and "Nitpick") on it incredibly fast.

The Big Hurdle: The Surjectivity Problem

Here is where the story gets tricky. The authors wanted to prove that the Lightweight Tent and the Deep Blueprint were actually saying the exact same thing. They wanted to show that if a statement is true in the Blueprint, it's true in the Tent, and vice versa.

But there was a snag. The Lightweight Tent uses a guide (a variable assignment) that can only point to a countable number of people (like the natural numbers: 1, 2, 3...). However, the Deep Blueprint allows for a universe with an uncountable number of people (like all the real numbers on a line).

If the universe is huge and uncountable, a guide that can only point to a countable list of people can't possibly reach everyone. It's like trying to call roll for a stadium of a billion people using a list that only has room for a thousand names. The authors realized that if they tried to force the guide to reach everyone in an uncountable universe, the proof would break.

The Magic Solution: The Downward Löwenheim–Skolem Theorem

To fix this, the authors didn't try to make the guide reach the uncountable crowd. Instead, they used a mathematical magic trick called the (countable) downward Löwenheim–Skolem theorem.

Think of it like this: The authors proved that for any giant, uncountable universe, there exists a smaller, countable "shadow" universe that acts exactly the same way for the logic we care about. It's like finding a perfect, miniature model of a massive city where every street corner and building behaves exactly like the real thing, but the model is small enough to fit on a desk.

They showed that even if the real world is uncountably huge, we can always shrink it down to this countable shadow. Since our Lightweight Tent's guide can reach everyone in this countable shadow, the bridge between the Tent and the Blueprint becomes solid again. The authors proved this works, meaning they didn't just guess or simulate it; they constructed a rigorous mathematical argument that holds up in Isabelle.

What They Didn't Do (The "No" List)

It's important to know what this paper doesn't do, so we don't get the wrong idea:

No Varying Domains: They didn't solve the problem where the list of people changes from world to world (like in some sci-fi stories where people are born or die between dimensions). They stuck to a constant domain, meaning the same set of people exists in every possible world.
No Equality: They didn't include a special "equals" sign ( $=$ ) in their logic. They focused on relationships between things, not on whether two things are identical.
No Infinite Worlds (Yet): To make their countable shadow work, they had to assume the number of worlds is also countable. They admitted that handling a universe with an uncountable number of worlds is a job for future work.

The Result: A Verified Connection

The authors didn't just suggest this works; they mechanized the proof inside Isabelle. They built the substitution machinery (the tools to swap variables without breaking things) and proved that:

The Deep Blueprint and the Lightweight Tent are faithful to each other.
You can prove things in the fast, lightweight Tent, and those proofs are guaranteed to be true in the heavy, detailed Blueprint.
They tested this by checking famous logic rules (like the K-axiom and the Barcan formulas) and confirming they hold up.

In short, the authors built a super-efficient, lightweight way to let a computer reason about complex "what-if" scenarios with quantifiers, and they mathematically proved that this shortcut doesn't skip any important details, even when the universe of possibilities is infinitely large. They turned a potential dead-end (the uncountable domain problem) into a solved puzzle using a clever mathematical shrinking trick.

Technical Summary: First-Order Modal Logic in HOL: Deep and Shallow Embeddings with Automated Faithfulness

Problem Statement
First-order modal logic (FML) combines the expressive power of quantification with modality, serving as a critical framework for applications in artificial intelligence, computer science, and philosophy. While embeddings of propositional modal logic (PML) into classical higher-order logic (HOL) have been successfully automated, extending these techniques to FML introduces significant complexity. Specifically, FML requires handling variable binding, substitution, and quantification over domains that may be uncountable. Previous work [5] established a deep-and-shallow embedding methodology for PML but did not address the substitution machinery or the surjectivity issues inherent in first-order quantification. The challenge lies in simultaneously providing a deep embedding (for syntactic reasoning) and shallow embeddings (for automated proof search) while proving their mutual faithfulness, particularly when the domain of individuals is uncountable and the variable assignment in the shallow embedding is restricted to a countable set (e.g., natural numbers).

Methodology
The authors extend the Isabelle/HOL environment to support FML under constant-domain Kripke semantics. The methodology employs three parallel embeddings:

Deep Embedding: Formulae are represented as an inductive datatype $\mathcal{F}$ . Truth is defined recursively over a model $\langle W, R, I, D \rangle$ , an assignment $g$ , and a world $w$ . Validity ($ValD$) quantifies universally over all models, assignments respecting the domain $D$ , and worlds.
Maximal Shallow Embedding: Formulae are lifted to $\lambda$ -terms explicitly abstracting over all model parameters ( $W, R, I, D, g, w$ ). This allows direct use of Isabelle's automation but results in complex types.
Minimal Shallow Embedding: Implemented as an Isabelle/HOL locale (MinS), this approach promotes static parameters ( $W, R, I, g$ ) to locale arguments, reducing the formula type to $w \Rightarrow bool$ . Crucially, the existential quantifier is encoded using Isabelle's native meta-level binder, while the modal operator shifts the world parameter.

To bridge the gap between the deep and minimal-shallow embeddings, the authors develop a comprehensive substitution machinery (free/bound variable predicates, capture-avoiding substitution, alphabetic renaming) necessary for handling first-order quantifiers, which was absent in the prior propositional work.

A central technical innovation is the mechanization of the countable downward Löwenheim–Skolem theorem for FML. This theorem guarantees that for any model and any countable initial sub-domain $D_0$ , there exists a countable elementary sub-domain $\mathcal{N}$ preserving truth. This is used to resolve the surjectivity problem: since the minimal-shallow assignment $g: V \to D$ (where $V = \mathbb{N}$ ) cannot be surjective onto an uncountable domain $D$ , direct faithfulness fails. By constructing a countable elementary sub-domain $\mathcal{N}$ onto which $g$ can be surjective, and proving that truth in $D$ coincides with truth in $\mathcal{N}$ , the authors recover faithfulness over the full domain.

Key Contributions

MinFMLinHOL Development: A complete Isabelle/HOL theory covering FML with binary relational atoms, propositional connectives, existential quantification, and the box modality under constant-domain semantics.
Three Embeddings: The provision of a deep embedding, a maximal shallow embedding, and a lightweight minimal shallow embedding (packaged as a locale).
Global Faithfulness Theorem: The introduction of the MinS locale allows for a strong global theorem, FaithfulMS_all, stating that quantifying over all minimal-shallow interpretations recovers exactly deep validity.
Substitution Machinery: The development of necessary syntactic tools (substitution lemmas, renaming, size-based induction) for the deep embedding of FML, extending the prior propositional work.
Mechanized Löwenheim–Skolem Theorem: A formalization of the downward Löwenheim–Skolem theorem for constant-domain Kripke semantics, which underpins the automation of the faithfulness proof between deep and minimal-shallow embeddings.
Surjectivity Resolution: The design of a refined locale MinS_surj that assumes the assignment is surjective onto an elementary sub-domain, lifting faithfulness from the range of the assignment to the full domain $D$ .

Results
The development is validated through several experiments:

Axiomatic Verification: Confirmation of the K-axiom, the necessitation rule, and the validity of both the Barcan and converse Barcan formulae (which hold under constant-domain semantics).
Frame Correspondences: Automated verification of correspondences between reflexive, transitive, and symmetric frames and the T, 4, and B axiom schemata.
Automation: The use of the sledgehammer and nitpick tools is demonstrated. The minimal-shallow embedding allows sledgehammer to treat first-order modal goals as ordinary HOL goals, while nitpick can find counterexamples by shrinking the domain type, effectively bypassing the explicit domain guards.

Significance
The paper claims that this work represents the natural extension of prior propositional embedding methodologies to the first-order case. Its primary significance lies in demonstrating that deep and shallow embeddings can coexist in a single HOL theory with automated faithfulness proofs, even in the presence of first-order quantification and uncountable domains. By leveraging the locale mechanism and the Löwenheim–Skolem theorem, the authors overcome the technical barrier of variable assignment surjectivity, enabling the use of powerful HOL automation tools for first-order modal logic without sacrificing the rigor of deep syntactic representation. The work establishes a foundation for future extensions, such as varying-domain semantics or the inclusion of equality, while currently focusing on the minimal constant-domain fragment.

The Three Bridges

The Big Hurdle: The Surjectivity Problem

The Magic Solution: The Downward Löwenheim–Skolem Theorem

What They Didn't Do (The "No" List)

The Result: A Verified Connection

More like this