Trivializing the Proof of Trivial Theorems

Yves Kodratoff, Jacqueline CastaingIJCAI 1983

Abstract

Automated theorem provers frequently struggle with inductive proofs that appear intuitive to humans. This paper introduces a "savage generalization" methodology: a top-down approach that intentionally over-generalizes a theorem until it becomes false, then utilizes small-value testing to identify the exact constraints required to render it both true and provable. By shifting the focus from "building up" generalizations to "pulling back" from over-generalization, the authors demonstrate a more efficient path for proving a specific class of recursive theorems.

Introduction: The Generalization Hurdle

In the field of automated theorem proving (ATP), induction remains a significant challenge. Even when a theorem is considered "trivial" by a mathematician, a computer system may encounter infinite loops or generate proof trees of impossible complexity. The primary obstacle is the requirement for generalization: to prove a statement by induction, one often must first prove a slightly more general version of that statement.

Traditional ATP systems typically attempt to generalize "upward" from specific cases. However, determining how to generalize without losing the theorem's core logic is difficult. Kodratoff and Castaing address this efficiency gap by proposing a method that flips the traditional approach on its head, specifically targeting a class of theorems they define as "trivial."

Methodology: Savage Generalization

The authors propose a four-step methodology designed to find the "sweet spot" of generality required for an inductive proof to succeed.

  1. Savage Generalization: The process begins by renaming every variable in the theorem to a unique name. This almost certainly renders the theorem false, but it establishes the maximum possible state of generalization.
  2. Progressive Particularization: The system tests this "broken" theorem against very small values (e.g., NIL or single-element lists). By observing where the evaluation fails, the system generates a system of equations. Solving these equations identifies which variables must be identical for the theorem to hold.
  3. Heuristic-Driven Matching: If the induction step fails to match the original theorem, the system identifies terms that do not contain the recurrence variable. These terms are replaced with new variables, creating a new candidate theorem.
  4. Lemma Induction: If the previous steps do not yield a direct proof, the system attempts to generate auxiliary lemmas by analyzing partial matches or specific values of the induction variable.

The transition from Step 1 to Step 2 is the core innovation. By over-generalizing and then narrowing down based on counter-examples, the system avoids the trial-and-error inherent in bottom-up generalization.

Theoretical Framework and "Triviality"

The paper utilizes a standard environment of recursive definitions, including list operations (EQL, APP, REV, CONS) and arithmetic (ZERO, SUCC). A central contribution of the work is the authors' specific definition of a "trivial" theorem. In this context, triviality is defined by behavior rather than simplicity:

  • Failure Speed: A theorem is trivial if it fails "quickly" on small values when it is false.
  • Solvability: The equations generated to fix a failed match must be "easy" to solve, typically through direct variable linking.

This leads to a philosophical pillar of the methodology: the coincidence of truth and provability. For this class of theorems, a version of the statement that is true for the smallest possible inputs is highly likely to be the version that is provable by induction.

Key Results and Case Study

The methodology was demonstrated through complex examples involving the interaction of REV (reverse), APP (append), and a recursive function FOO. In standard automated systems, induction on such theorems is often non-trivial and prone to failure.

By applying Step 1, the system generates a generalized version of the theorem. Through testing with NIL, the system discovers necessary constraints (e.g., identifying that specific variables must be unified). This results in a new theorem that, while appearing more complex to a human, is significantly easier for a computer to prove because the induction step matches the goal state perfectly.

Limitations and Conclusion

The authors acknowledge that their definition of "easy to solve" equations is somewhat implementation-dependent. Furthermore, the steps involving lemma induction (Steps 3 and 4) rely more heavily on heuristics than the more rigorous first two steps.

Despite these limitations, the "savage generalization" approach provides a robust framework for handling inductive proofs. By jumping to a state of maximum generality and using counter-examples to "pull back" to the truth, the system successfully trivializes proofs that were previously considered difficult for automated provers.

Summary updated

BibTeX
@inproceedings{kodratoff1983trivializing,
  author = {Yves Kodratoff and Jacqueline Castaing},
  title = {{Trivializing the Proof of Trivial Theorems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure