Abstract
This paper addresses a critical bottleneck in automated theorem proving: the selection and combination of induction axioms. We describe a method for automatically merging multiple induction rules into a single, more expressive axiom. By leveraging commutation tests from term rewriting theory, the system can formally verify that these combined rules remain well-founded. This approach, implemented in the INKA prover, allows for the automated discovery of complex inductive proof strategies that would otherwise require manual intervention.
Introduction
In automated verification, induction is the primary tool for reasoning about recursive structures and programs. Proving a statement requires selecting an induction axiom—a rule that specifies the induction hypotheses. A common failure mode occurs when no single heuristic-suggested axiom is sufficient, but a combination of them would be. However, blindly merging axioms is dangerous; the union of two well-founded relations is not guaranteed to be well-founded, which can lead to logically unsound proofs.
Methodology
Christoph Walther proposes a framework to safely merge these rules using a "separated union" of relation descriptions ($r$-descriptions). The core innovation is the use of automated commutation tests to ensure the resulting axiom is sound. Rather than attempting a direct proof of well-foundedness, the system generates "commutation formulas"—logical statements that, if true, guarantee the combined axiom is well-founded.
The theorem prover then uses its own internal logic to verify these formulas. This "meta-logic via base-logic" approach allows the prover to bootstrap its capabilities autonomously. The system specifically checks for properties like quasi-commutation, which provides a sufficient condition for the union of two relations to remain well-founded.
Results and Implementation
The technique was integrated into the INKA induction theorem prover, a state-of-the-art system at the time. Evaluation on classic recursive functions (e.g., arithmetic operations like quot, half, plus, and minus) demonstrated that the system could successfully prove theorems where individual heuristics failed. The commutation tests are computationally efficient, often requiring only simple propositional reasoning and case analysis, making them much cheaper than a full-blown direct proof of well-foundedness.
Conclusion
The proposed method provides a "safe" expansion of the proof search space: a proof using a combined axiom will succeed whenever a proof using any of its components would have. By combining axioms, the prover gains access to more induction hypotheses simultaneously, which is often the missing link in complex verification problems. While the system still relies on initial heuristics to suggest parent axioms, the ability to automatically synthesize and verify more powerful rules represents a significant step forward in automated formal methods.
Summary updated