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

2026-07-12 · Source: Artificial Intelligence · Field: Science & Research — Mathematics & Computational Sciences, Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

This extended preprint details an advancement in formal logic, extending a deep-and-shallow embedding methodology within Isabelle/HOL from propositional to first-order modal logic (FML) with constant-domain Kripke semantics. The work introduces three distinct embeddings: a deep embedding, a heavyweight maximal-shallow embedding, and a lightweight minimal-shallow embedding. A significant contribution is the minimal-shallow embedding, structured as an Isabelle/HOL locale, which enables a global faithfulness theorem linking it to deep validity. Crucially, the authors mechanize the countable downward Löwenheim-Skolem theorem for FML, a technical feat that automates the faithfulness proof between the deep and minimal-shallow embeddings. This mechanization addresses the surjectivity problem arising from uncountable domains of individuals, ensuring faithfulness across the full domain. Additionally, the research develops comprehensive substitution machinery, including free/bound-variable predicates and capture-avoiding substitution, essential for handling first-order quantifiers not covered in previous propositional work.

Key takeaway

For research scientists working with formal verification or automated theorem proving in higher-order logic, this work demonstrates a robust methodology for extending propositional logic frameworks to first-order modal logic. You should consider how mechanizing theorems like Löwenheim-Skolem can automate complex faithfulness proofs, particularly when dealing with domain surjectivity challenges. This approach offers a blueprint for developing more expressive and verifiable logical systems within environments like Isabelle/HOL.

Key insights

Automated faithfulness between deep and shallow embeddings of First-Order Modal Logic is achieved via the Löwenheim-Skolem theorem.

Principles

• Deep and shallow embeddings can be formally linked.
• Löwenheim-Skolem theorem resolves domain surjectivity issues.
• Isabelle/HOL locales enable global faithfulness theorems.

Method

The method involves extending deep-and-shallow embedding to FML, mechanizing the downward Löwenheim-Skolem theorem, and developing substitution machinery for first-order quantifiers within Isabelle/HOL to prove automated faithfulness.

Topics

• First-Order Modal Logic
• Isabelle/HOL
• Deep and Shallow Embeddings
• Löwenheim-Skolem Theorem
• Kripke Semantics
• Automated Theorem Proving

Best for: AI Scientist, Research Scientist

Related on AIssential

• Reasoning about concurrent loops and recursion with rely-guarantee rules — Mechanically verified rely-guarantee rules enable compositional reasoning for concurrent loops and recursion without assuming atomic expression evaluation.
• From Natural Language to Certified Geometry Proofs: A Survey of LLM-Augmented Verification and Neuro-Symbolic Theorem Proving — LLM-symbolic hybrid systems combine LLM flexibility with symbolic rigor for certified geometry proofs.
• Abduction Prover in Isabelle/HOL — Abductive reasoning enhances proof automation in expressive logic-based proof assistants.
• The Faithfulness Gap: Certifying Semantic Equivalence Between Natural-Language and Formal Mathematical Statements — Certifying semantic equivalence between natural language and formal math statements is crucial for autoformalization faithfulness.
• Isabelle/HOL: The proof assistant behind the Nitro Isolation Engine — Isabelle/HOL's balance of expressiveness and automation enabled the formal verification of AWS's Nitro Isolation Engine.
• A New Well-Supported Semantics for Description Logic Programs — The new semantics for Description Logic Programs offers reduced computational complexity and a clear characterization, improving upon prior well-supported semantics.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Artificial Intelligence.