Mechanising Böhm Trees and λη-Completeness

Chun Tian, Michael NorrishITP 2025 · DOI

TL;DR

This paper presents the first formal mechanization of the Hilbert-Post completeness of the $\lambda\eta$-equational theory using the HOL4 theorem prover. By developing novel techniques for handling Böhm trees and fresh name generation, the authors provide a verified proof of a fundamental result in lambda calculus theory, paving the way for further formal verification of complex lambda calculus properties.

What Problem Does This Paper Address?

The untyped lambda calculus is a foundational concept in computer science, but many of its fundamental results, particularly those concerning equational theories and completeness, remain unverified by formal proof assistants. This lack of mechanization means that subtle errors or omissions in existing proofs, like those found in Barendregt's seminal work, can go unnoticed. Specifically, this paper tackles the challenge of formally proving the $\lambda\eta$-completeness of the lambda calculus, a result that establishes that the equational theory proves all compatible equations between $\beta\eta$-normal forms. This requires a rigorous formalization of Böhm trees, which are crucial for understanding the semantics of $\beta$-reduction and proving completeness, and handling the complexities of $\alpha$-equivalence.

Methods

The authors employ the HOL4 theorem prover to mechanize their proofs. Their approach involves:

  • Coinductive Definition of Böhm Trees: They introduce a coinductive definition for Böhm trees, which are essential for capturing the semantics of $\beta$-reduction and are structured as potentially infinite trees.
  • "Böhm Out" Technique: This technique is used to retrieve subterms corresponding to specific paths within a Böhm tree. The paper formalizes this by developing "solving transforms" and "Böhm transformations" that allow for the manipulation of lambda terms to extract subterms.
  • Novel Fresh Name Allocation: To manage the complexities of $\alpha$-equivalence within Böhm trees, they develop a new technology called RNEWS for allocating fresh names. This system provides stronger guarantees than existing nominal packages, crucial for maintaining inductive invariants.
  • Formalization of Wadsworth's Solvability Theorem: As a related result and a stepping stone, they mechanize the proof that terms with head-normal forms are exactly those that are solvable.
  • Simplification of Barendregt's Approach: The authors aim to simplify Barendregt's original proof by avoiding direct comparison of Böhm trees and leveraging more modern proofs about $\eta$-reduction.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Böhm Trees as Coalgebraic Structures: The paper highlights that the potentially infinite nature of Böhm trees makes them naturally suited for a coalgebraic perspective, which is leveraged in their HOL4 formalization.
  • The Importance of Fresh Name Generation: The development of RNEWS demonstrates that robust and well-characterized fresh name generation is critical for formalizing complex inductive structures like Böhm trees, especially when dealing with $\alpha$-equivalence.
  • "Böhm Out" as a Powerful Tool: The formalization of the "Böhm out" technique provides a rigorous way to relate terms to their subterms via Böhm trees, which is instrumental in proving equational properties.
  • Mechanization Enables Simplification: By formalizing the underlying concepts, the authors were able to simplify aspects of Barendregt's original proof, such as avoiding direct Böhm tree comparisons.

Key Results

  • First Mechanization of $\lambda\eta$-Completeness: The paper presents the first formal, machine-checked proof of the Hilbert-Post completeness of the $\lambda\eta$-equational theory for untyped lambda calculus.
  • Formalization of Böhm Trees and Subterms: A complete formalization of Böhm trees and their subterms within HOL4 is provided, including novel techniques for handling free variables and $\alpha$-equivalence.
  • Mechanized Proof of Wadsworth's Solvability Theorem: The paper includes a verified proof of the theorem stating that terms with head-normal forms are exactly those that are solvable.
  • Development of RNEWS: A new technology for allocating fresh names with specific properties is introduced, which is crucial for the formalization of Böhm trees.

Limitations and Future Work

  • Complexity of Proofs: The authors acknowledge that the formalization of Böhm trees and related lemmas, particularly Lemma 23 ("subtree_equiv_lemma"), involved a significant amount of HOL script (around 4,000 lines) and took considerable time to complete.
  • Future Work on Böhm Trees: The paper suggests that Böhm trees are a powerful abstraction that can be used for further analysis, such as in the study of models like $P_\omega$ and $D_\infty$.
  • Separability Theorems: The authors mention that proving Böhm's original (β-)separability theorem and general separability results for more than two terms are remaining tasks.
  • Virtual Böhm Tree Nodes: The need for "extra proofs (involving virtual Böhm tree nodes)" for the separability theorem is noted.

Summary updated

BibTeX
@inproceedings{tian2025mechanising,
  author = {Chun Tian and Michael Norrish},
  title = {{Mechanising Böhm Trees and λη-Completeness}},
  booktitle = {ITP},
  year = {2025},
  doi = {10.4230/lipics.itp.2025.28},
}
Figure