Automating proof search when equality is a logical connective
Kaustuv Chaudhuri & Arunava Gantait & Dale Miller · 2026
Read Automating proof search when equality is a logical connective by Kaustuv Chaudhuri & Arunava Gantait & Dale Miller (2026) 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-2605-20054.txt.
Introduction
Kaustuv Chaudhuri, Arunava Gantait and Dale Miller build proof search where syntactic equality acts as a logical connective. With left- and right-rules in the sequent calculus, this treatment derives core laws such as Peano's axioms without induction and backs the Abella proof assistant. Their method extends unification to quantifier switches and equations on both sides. It enables unification-aware search across diverse first-order sequent calculi that use this equality.
Catalog record
| CREATOR | Kaustuv Chaudhuri & Arunava Gantait & Dale Miller |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49576 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.20054
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Automating proof search when equality is a logical connective Kaustuv Chaudhuri & Arunava Gantait & Dale Miller Abstract Treating syntactic equality as a logical connective—governed by left- and right-introduction rules within the sequent calculus—offers an elegant and powerful approach to term identity. This treatment of equality allows for the derivation of core mathematical principles, such as Peano’s axioms (excluding induction), and serves as a foundation for the Abella interactive proof assistant. However, integrating this equality into automated proof search remains challenging. We present a proof search procedure that extends unification to handle the complexities of quantifier alternation and equations that occur in both positive and negative occurrences. While established logical frameworks such as λ \lambda Prolog and LF lack direct support for this kind of equality, our procedure enables a lightweight logical framework that addresses this gap. Our system enables unification-aware proof search across a diverse range of first-order sequent calculi that can directly use this form of equality. 1 Introduction Logical frameworks [ 19 ] typically employ a term language based on the \lambda -calculus equipped with a notion of equality (written = ) derived from \alpha\beta\eta -conversion. Implementing such a logical framework requires the ability to reason about this equality in the presence of unknowns, i.e., over open terms. For instance, unification problems can be represented as a finite list of (disagreement) pairs of terms [\langle t_{1},s_{1}\rangle,\dotsc\langle t_{n},s_{n}\rangle] , where all free variables are contained in the list \bar{x}=x_{1},\dotsc,x_{m} . A solution to such a unification problem is a substitution \theta for the variables \bar{x} such that t_{i}\theta=s_{i}\theta , for every i\in\{1,\dotsc,n\} . Such a unification problem can therefore be formally depicted as the logical formula: \displaystyle\exists x_{1}.\,\dotsm\exists x_{m}.\,\left(t_{1}=s_{1}\land\dotsm\land t_{n}=s_{n}\right). In logical frameworks supporting proof search , such as \lambda Prolog [ 11 ] and Twelf [ 17 ] , these problems are generalized to include two kinds of variables: logic variables , which arise from existential quantification and must be instantiated with terms, and eigenvariables (aka universal variables and parameters ), which arise from universal quantification and are treated as pairwise distinct. These generalized problems take the form: \displaystyle\mathcal{Q}_{1}x_{1}.\,\dotsm\mathcal{Q}_{m}x_{m}.\,\left(t_{1}=s_{1}\land\dotsm\land t_{n}=s_{n}\right) where each \mathcal{Q}_{i} is either \forall or \exists . Frameworks for solving unification problems of this “mixed prefix” form were developed in the early 1990s [ 14 , 15 , 16 , 18 ] . In the aforementioned frameworks, equality arises during the process of logical reasoning within the framework, but equality is not itself reified as a logical connective. However, Girard [ 7 ] and Schroeder-Heister [ 20 ] both proposed, in the early 1990s, a proof-theoretically elegant approach to first-order term equality as a logical connective, in the sense that it was given left- and right-introduction rules in a sequent calculus formulation that worked well with cut-elimination. This treatment was subsequently extended to deal with simply-typed \lambda -terms [ 9 , 12 ] and was implemented in the Bedwyr model checker [ 2 ] and the Abella proof assistant [ 1 ] . Motivated by the automation of proof search in Abella, we find it necessary to address unification problems that are more expressive than standard mixed prefix unification problems. We develop this richer unification setting in the present paper. When equality is treated as a logical connective, each conjunct in the mixed prefix unification problem may involve a collection of equality antecedents, so the problems now have the following shape: \displaystyle\mathcal{Q}_{1}x_{1}.\,\dotsm\ \mathcal{Q}_{m}x_{m}.\,\bigwedge_{i\in\{1,\dotsc,n\}}\left(t_{i,1}=s_{i,1}\supset\dotsm\supset t_{i,k_{i}}=s_{i,k_{i}}\supset t_{i}=s_{i}\right). We also must restrict the provability of such formulas to intuitionistic (and not classical) logic. In order to increase the utility of our framework, we also permit atomic formulas defined via logic-programming-style definitions . We use these to define derivability of essentially any first-order object logic by defining provability in some sequent calculus via a recursive definition, as detailed in Section 3 . The inclusion of atomic formulas requires us to consider search problems of the following shape: \displaystyle\mathcal{Q}_{1}x_{1}.\,\dotsm\mathcal{Q}_{m}x_{m}.\,\bigwedge_{i\in\{1,\dotsc,n\}}\left(t_{i,1}=s_{i,1}\supset\dotsm\supset t_{i,k_{i}}=s_{i,k_{i}}\supset H_{i}\right), where each H_{i} is either an equality or a (defined) atom. Automating problems of this shape is a significant challenge. Derivability for such formulas is undecidable even when restricted to first-order terms and empty definitions. Furthermore, reasoning about equality in the heads H_{i} necessitates backtracking search (e.g. via Huet’s algorithm [ 8 ] ), which is only a semi-decision procedure. Due to the mixed prefix, neither the positive nor the negative occurrences of equalities can be fully solved in isolation; instead, partial solutions must be communicated between the conjuncts of the problem, so that a conjunct that is otherwise stuck may continue to ensure progress. In this paper, we introduce a proof search procedure designed to manage complex unification scenarios involving quantifier alternation and equations in both positive and negative occurrences. We extend this procedure to incorporate atomic formulas defined via logic programming-style specifications. This extension yields SLIM (Specification Logic based on an Intuitionistic Metalogic), a lightweight logical framework developed to provide the direct support for equality often absent in established systems. Finally, we present a sound and relatively complete non-deterministic algorithm for proof search in SLIM sequents, formalized as a state transition system. We conclude by discussing how SLIM can be leveraged to provide the Abella system with more robust automated proof search. 2 The LJ {}^{=}_{\omega} logic and its proof system This section will present an intuitionistic logic LJ {}^{=}_{\omega} that is a subset of Church’s Simple Theory of Types [ 3 ] and provide it with a proof system based on Gentzen’s LJ proof system [ 5 ] . The subscript \omega in the name LJ {}^{=}_{\omega} indicates that typed quantified variables can be of arbitrary order. Eventually we will identify a subset of this logic that we shall consider as our lightweight logical framework: in that subset, the order of typed quantified variables will be limited to be 0 or 1. 2.1 Types, terms, and formulas Types (written \sigma or \tau ) consist of primitive types including the primitive type o of formulas (following Church’s convention) and other primitive types that are declared when we have a need for them; and arrow types \sigma\rightarrow\tau with \rightarrow being right-associative. The order of a type \sigma , written \text{ord}(\sigma) , is defined to be 0 if \sigma is a primitive type, and \text{ord}(\sigma\rightarrow\tau)=\max(\text{ord}(\sigma)+1,\text{ord}(\tau)) . For a type \sigma=\sigma_{1}\rightarrow\dotsm\rightarrow\sigma_{n}\rightarrow\tau where \tau is a primitive type, we say that \sigma_{1},\dotsc,\sigma_{n} are the argument types of \sigma and \tau is its target type . Note that if \text{ord}(\sigma)\leq 1 , then every argument type of \sigma is a primitive type. These types are inhabited by \lambda -terms with the usual syntax and typing rules, which we elide in this paper. Following Church, logic is introduced to this simple type theory by declaring the following logical constants, together with their associated types: \displaystyle\boldsymbol{t},\boldsymbol{f}:o,\quad{\wedge},{\vee},{\supset}:o\rightarrow o\rightarrow o,\quad=_{\sigma}\colon\sigma\rightarrow\sigma\rightarrow o,\quad{\forall_{\sigma}},{\exists_{\sigma}}:(\sigma\rightarrow o)\rightarrow o. We will write \wedge , \vee , \supset , and =_{\sigma} infix, with the usual conventions. We will also abbreviate \forall_{\sigma}(\lambda x.\,F) and \exists_{\sigma}(\lambda x.\,F) as \forall_{\sigma}x.\,F and \exists_{\sigma}x.\,F respectively. Finally, we will drop the type-suffixes on quantifiers and equality if they are clear from context or unimportant to the exposition. These logical constants will be given a meaning in terms of inference rules in a sequent calculus in the next subsection. The