Automating Proof Search when Equality is a Logical Connective
Open Access
- 24 July 2026
- book chapter
- Published by Springer Nature
- p. 73-90
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.
Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Functions-as-constructors higher-order unification: extended pattern unificationAnnals of Mathematics and Artificial Intelligence, 2021
- The undecidability of proof search when equality is a logical connectiveAnnals of Mathematics and Artificial Intelligence, 2021
- Translating Between Implicit and Explicit Versions of Proof2017
- The Proof Certifier Checkers2015
- The Bedwyr System for Model Checking over Syntactic ExpressionsLecture Notes in Computer Science, 2007
- Specifying theorem provers in a higher-order logic programming language2005
- System Description: Twelf — A Meta-Logical Framework for Deductive Systems1999
- A proof procedure for the logic of hereditary Harrop formulasJournal of Automated Reasoning, 1993
- Paramodulation and Theorem-Proving in First-Order Theories with Equality1983
- Untersuchungen ber das logische Schlie en. IMathematische Zeitschrift, 1935