Commenting Proofs

James R. GeiserIJCAI 1975

In 1974, James R. Geiser of the MIT Artificial Intelligence Laboratory proposed a method to bridge the gap between the rigid syntax of formal logic and the pragmatic intent of human reasoning. His report, "Commenting Proofs," introduces a framework for tracking the "causal history" of mathematical symbols—essentially answering the question: "Which part of the input is responsible for this specific part of the output?"

The Problem of Accountability in Logic

Traditional formal logic treats a proof as a sequence of sentences following syntactic rules. While this ensures correctness, it often obscures the "why" and "how" of the computation. For instance, in Peano Arithmetic using "stroke" notation (where 3 is represented as |||), a calculation like $11 \times 111 = 111111$ confirms the result but fails to track which specific stroke in the input corresponds to a specific stroke in the output.

Geiser identifies this as a lack of accountability in formal proofs. He aims to create a semantics that accounts for the "real" process of proof construction—where a mathematician has a goal in mind—and provides a way to trace the "causal history" of every symbol in a final result back to its origins.

Methods: Enriching Formal Proofs

Geiser's system enriches proofs with three layers of metadata to restore this missing context. First, he distinguishes between Intrinsic and Extrinsic Commenting. Intrinsic comments note the formal rule applied (e.g., "this line follows from Axiom A2"), while extrinsic comments describe the goal-oriented purpose of a step (e.g., "this line is generated to simplify a term").

Second, he introduces Identificational Connections (ids). These are pointers establishing "synonymity" between symbols across different lines, creating a causal chain. Finally, he defines Ingredients, a list structure representing the computational history of a specific part of a term. The paper utilizes algebraic mappings, or homomorphisms, to demonstrate how these ingredients are transformed or preserved as a term is evaluated, ensuring that the structural integrity of the causal history is maintained throughout the proof.

Figure 3: Axioms for addition, multiplication, and exponentiation enriched with identificational connections (arrows) to track symbol provenance.

As shown in Figure 3, the "ids" (represented by arrows) map how variables and constants transition through axioms. This allows the system to maintain a "biography" for every symbol as it moves through a computation.

Key Insights: Path Invariance and Convergence

A central contribution of the paper is the concept of Path Invariance (Theorem 7.7). Geiser demonstrates that the "ingredients" of a result—its computational lineage—remain invariant regardless of the specific sequence of reductions or simplifications taken to reach it. Whether a mathematician takes a direct or a roundabout "computation path" to solve an equation, the underlying causal relationship between the input symbols and the output symbols remains the same.

Figure 5: A detailed look at the identificational connections for the multiplication axiom M2, showing how the term 't' is distributed and tracked.

This invariance is supported by an analogue to the Church-Rosser theorem (Lemma 5.3), which ensures that different sequences of simplifications eventually converge to the same result. This ensures that the "causal history" is not a fragile artifact of a specific proof path but a robust property of the logic itself.

Conclusion and Future Directions

Geiser’s work treats proofs as programs, aligning with the procedural interpretation of logic popularized by early AI languages like PLANNER. While the 1974 framework was limited to Primitive Recursive Arithmetic, it laid the groundwork for tracing data provenance in complex deductive systems. Geiser suggested that these "ingredients" could eventually help explore concepts like consistency and "relevant entailment"—the idea that premises must be meaningfully utilized to justify a conclusion.

Summary updated

BibTeX
@inproceedings{geiser1975commenting,
  author = {James R. Geiser},
  title = {{Commenting Proofs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1975},
}
Figure