Faithful Logic Embeddings in HOL — Deep and Shallow
Christoph Benzmüller · 2025
Read Faithful Logic Embeddings in HOL — Deep and Shallow by Christoph Benzmüller (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-19311.txt.
Introduction
Christoph Benzmüller writes a 2025 logic paper on two ways to place non-classic logics inside classic higher-order logic. Deep placement rebuilds a logic's grammar step by step. Shallow placement maps its phrases straight onto host phrases.
Each style has its own strengths for proof tools. Benzmüller gives a method to run both at once, at several depths, in the same system. That allows proof search and counter-example search at both the host and guest level. It also allows machine-checked proof that the two placements agree. He shows the method on a simple modal logic and notes gains for teaching, research, and applied reasoning.
Catalog record
| CREATOR | Christoph Benzmüller |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19311
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faithful Logic Embeddings in HOL — Deep and Shallow Christoph Benzmüller Abstract Deep and shallow embeddings of non-classical logics in classical higher-order logic have been explored, implemented, and used in various reasoning tools in recent years. This paper presents a method for the simultaneous deployment of deep and shallow embeddings of various degrees in classical higher-order logic. This enables flexible, interactive and automated theorem proving and counterexample finding at meta and object level, as well as automated faithfulness proofs between these logic embeddings. The method is beneficial for logic education, research and application and is illustrated here using a simple propositional modal logic. However, this approach is conceptual in nature and not limited to this simple logic context. 1 Motivation and Introduction Deep embeddings of logics, or more generally of domain-specific languages, in a suitable metalogic, such as classical higher-order logic (HOL) [ 26 , 5 ] , are typically based on explicitly introduced abstract data types. They essentially axiomatically characterize the structure and the meaning of the new language. Shallow embeddings, on the other hand, identify the embedded languages directly as fragments of the metalogic and they typically require few or no axiom postulates. 1 1 1 Gibbons and Wu characterize the two notions as follows [ 33 , p.2] : “[…] a deep embedding consists of a representation of the abstract syntax as an algebraic datatype, together with some functions that assign semantics to that syntax by traversing the algebraic datatype. A shallow embedding eschews the algebraic datatype, and hence the explicit representation of the abstract syntax of the language; instead, the language is defined directly in terms of its semantics.” Deep and shallow embeddings of logics in HOL effectively and elegantly support interactive and automated reasoning with and about such logics within existing HOL theorem proving systems. Consequently, they have received increased attention in recent years. Shallow embeddings, for example, are well suited to automate even quantified modal logics, enabling applications in areas such as computational metaphysics [ 15 ] . Deep embeddings, on the other hand, are well suited to enable reasoning about the syntactic structure of embedded logics. The contributions of this paper are manifold: First, a technique for the simultaneous provision of deep and shallow embeddings in metalogic HOL is presented, with the effect that computer-supported faithfulness proofs between the embeddings are not only enabled, but may — at least for simple embedded logics — now even be fully automated in HOL. This is, to the best of the authors’ knowledge, a novel result. Second, this paper discusses shallow embedding alternatives differing in the degree of semantic dependencies that are explicitly encoded and maintained. More precisely, heavyweight (maximal) and lightweight (minimal) shallow embeddings are contrasted as extremes, and doing so, the paper hints at the full spectrum that exists between these extremes, which is in fact relevant for practice. For example, while a minimal shallow embedding for a normal modal logic only needs to explicitly encode the crucial semantic dependency on possible worlds [ 10 ] , the explicit maintenance of an additional dependency, namely on dynamically updated domains of possible worlds, becomes relevant in case the logic is extended by a public announcement operator [ 12 ] . Third, the paper hints at opportunities for logic education, and for research, about and with logic embeddings within modern proof assistants and theorem provers for HOL. These range from metalogical studies to object logic applications using interactive proof and disproof, as well as automated theorem proving and counterexample finding, while allowing precise control over the particular level (object- or metalevel) at which reasoning takes place. Fourth, the paper presents some preliminary studies on whether shallow or deep embeddings are better suited for certain reasoning tasks. Fifth, using the Löb axiom of provability logic, the paper briefly sketches how research on the detection of semantic correspondences could possibly be supported by the presented technique in the future. Since this paper and associated material is intended to be used in logic education, simple propositional modal logic (PML) [ 32 , 17 , 54 ] has been chosen to illustrate the addressed ideas, and Isabelle/HOL [ 48 ] has been chosen as the host proof assistant system for the experiments conducted. Reasons for using Isabelle/HOL include (i) its very good proof automation support with e.g. the sledgehammer [ 18 ] tool, (ii) the availability of the (counter-)model finder nitpick [ 19 ] , and (iii) its powerful user interface, which allows for user-friendly L a T e X -quality representations. In principle, this paper could have taken advantage of Isabelle/HOL’s special support for computer-verifiable paper writing to generate a document directly from the Isabelle/HOL sources, as is the case, for example, with all the articles published in the Archive of Formal Proofs. However, the author has decided against this idea and in favor of screenshots of the source code in order to save space. Furthermore, the visual highlighting and indenting in these screenshots makes them more useful for teaching and illustration purposes by drawing attention to the most important information. Organization of the paper: § 2 and § 3 briefly introduce PML and HOL, before § 4 - 6 present deep, maximally shallow, and minimally shallow embeddings of PML in HOL. These are connected by automated faithfulness proofs given in § 7 . Various experiments with the presented embeddings are presented in § 8 , before § 9 discusses related work and § 10 concludes the paper. 2 Propositional modal logic (PML) The syntax of PML is defined by the grammar \varphi,\psi:=a\mid\neg\varphi\mid\varphi\supset\psi\mid\Box\varphi , where a\in\mathcal{S} are propositional symbols declared in a (nonempty) signature \mathcal{S} . Further logical connectives can be defined as usual, e.g.: \varphi\vee\psi:=\neg\varphi\supset\psi , \varphi\wedge\psi:=\neg(\varphi\supset\neg\psi) , \Diamond\varphi:=\neg\Box\neg\varphi , \top:=p\supset p (for some p\in\mathcal{S} ), and \bot:=\neg\top . A semantics for PML, called relational semantics or possible-world semantics, determines the truth of a formula \varphi relative to a so-called possible world w and a relational model \mathcal{M} . A relational model \mathcal{M} is a tuple \langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle , where \mathcal{W} is a set of possible worlds (the universe), \mathcal{R} is a binary relation on W (called the accessibility relation), \mathcal{V} is a valuation function that assigns a truth value to each symbol a\in\mathcal{S} in each world w\in\mathcal{W} , where \mathcal{S} is the signature of propositional symbols. \langle\mathcal{W},\mathcal{R}\rangle is called a frame . Formally, the truth of a formula \varphi with respect to a given model \langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle and a possible world w\in\mathcal{W} is defined as follows: \displaystyle\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w \displaystyle\models a\text{\ iff\ }\mathcal{V}(a)(w)\text{\ is true} \displaystyle\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w \displaystyle\models\neg\varphi\text{\ iff\ not\ }\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w\models\varphi \displaystyle\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w \displaystyle\models\varphi\supset\psi\text{\ iff\ }\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w\models\varphi\text{\ implies\ }\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w\models\psi \displaystyle\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w \displaystyle\models\Box\varphi\text{\ iff\ for\ all\ }v\text{\ with\ }\mathcal{R}wv\text{\ we have\ }\langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,v\models\varphi Note that in this recursive definition of truth the only parameter altered is the possible world w in the \Box -clause, which states that a formula \varphi is ‘necessary’ in a world w if and only if (iff) \varphi is true at all worlds v that are reachable from w via the accessibility relation \mathcal{R} . Based on the above definitions a notion of validity can be defined: A formula \varphi is valid (in so called base modal logic K ) iff \langle\mathcal{W},\mathcal{R},\mathcal{V}\rangle,w\models\varphi for all \mathcal{W} , \mathcal{R} , \mathcal{V} , and w\in\mathcal{W} .