A Theorem Prover for Elementary Set Theory

Frank M. BrownIJCAI 1977

TL;DR

This paper presents an automated theorem prover for elementary set theory that operates by treating mathematical proofs as a series of truth-value preserving transformations. By using a "call-by-need" interpreter and a specialized set of rewrite rules based on Quine’s set theory, the system successfully proved Cantor’s Theorem in less than two seconds on 1970s hardware.

What Problem Does This Paper Address?

In the mid-1970s, automated theorem proving was a burgeoning field, but set theory posed a significant challenge. The sheer flexibility of set-theoretic definitions and the infinite search space for proofs made traditional "brute force" logic engines inefficient.

F.M. Brown sought to bridge the gap between general-purpose logic and specialized mathematical intuition. The challenge was to create a system that didn't just shuffle symbols blindly but "understood" mathematical domains—specifically the distinction between a general property (an "abstract") and an object that actually exists in the universe of discourse (a "set").

Methods

The author describes a system built in UCI LISP that functions more like a mathematical interpreter than a traditional search-based prover. Key components include:

  • Truth-Value Preserving Transformations: The prover views a theorem as an expression to be simplified. It applies "items of knowledge" (rewrite rules) of the form $\phi \leftrightarrow \psi$ to reduce complex statements into simpler ones.
  • Call-by-Need Evaluation: The interpreter evaluates theorems recursively. It tries to apply its library of mathematical knowledge to a sub-expression before evaluating the arguments, preventing unnecessary computation.
  • Conditional Items: Some rules are only valid in specific sub-domains (e.g., only for sets, not for all abstracts). The system uses a "forcing strategy" to match these conditions against known truths.
  • Quine’s Logic: The system is specifically modeled on the set theory described in W.V.O. Quine’s Set Theory and its Logic (1969). This framework distinguishes between "abstracts" $\{x : Fx\}$ and "sets" (abstracts that exist).
  • Quantifier Strategies: To handle the "explosion" of variables, the paper introduces a "Creation Strategy" for instantiating quantifiers only when necessary and a "Forcing Strategy" to prioritize substitutions that make a statement a tautology.

Datasets

As is typical for 1970s formal methods research, there are no large-scale datasets or benchmarks in the modern sense. Instead, the system is evaluated on its ability to produce a formal proof for a landmark mathematical statement: Cantor's Theorem (the power set of a set has a strictly greater cardinality than the set itself).

Key Insights and Ideas

  • Proof as Evaluation: The most striking idea is treating a proof as a program execution. By using a "call-by-need" interpreter, the system avoids the "state-space explosion" that plagues many breadth-first search provers.
  • Domain-Specific Variables: To minimize the cost of matching rules, the prover uses different styles of variables (Roman for sets, Greek for general abstracts). This "type-hinting" allows the interpreter to quickly discard irrelevant rules.
  • Delaying the "Split": The system is designed to delay "splitting" (case analysis) as long as possible. By working on assertions first and simplifying the expression, it keeps the proof tree narrow and manageable.

Key Results

  • Cantor’s Theorem: The system successfully generated a complete, step-by-step proof protocol for Cantor’s Theorem.
  • Efficiency: The proof was obtained in 1.494 seconds on a DEC10 computer with a KA10 CPU. For the era, this was exceptionally fast, demonstrating that a well-tuned interpreter could outperform general-purpose resolution provers.
  • Compactness: The author emphasizes that the program is "fast and compact," suggesting that the logic-as-transformation approach is more computationally efficient than pure search.

Limitations and Future Work

  • Termination Issues: The author admits that while reduction lemmas usually simplify expressions, there is no formal guarantee that the system won't enter an infinite loop if given pathological rewrite rules.
  • Heuristic Dependency: The success of the proof depends heavily on the order in which rules are applied. While the "forcing" and "creation" strategies help, a different ordering of the same rules might fail to find a proof.
  • Narrow Domain: While successful in Quine’s set theory, the paper notes that extending this to other mathematical domains (like general arithmetic) was a separate, ongoing effort (referenced as Brown [1976]).

Summary updated

BibTeX
@inproceedings{brown1977theorem,
  author = {Frank M. Brown},
  title = {{A Theorem Prover for Elementary Set Theory}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure