Lean-auto: An Interface between Lean 4 and Automated Theorem Provers
Yicheng Qian, Joshua Clune, Clark Barrett, Jeremy Avigad
cs.LO
May 20, 2025 · v1
TL;DR
Lean-auto translates Lean 4's dependent type theory to automated theorem provers, enabling general-purpose ATP-based proof automation.
Abstract
Proof automation is crucial to large-scale formal mathematics and software/hardware verification projects in ITPs. Sophisticated tools called hammers have been developed to provide general-purpose proof automation in ITPs such as Coq and Isabelle, leveraging the power of ATPs. An important component of a hammer is the translation algorithm from the ITP's logical system to the ATP's logical system. In this paper, we propose a novel translation algorithm for ITPs based on dependent type theory. The algorithm is implemented in Lean 4 under the name Lean-auto. When combined with ATPs, Lean-auto provides general-purpose, ATP-based proof automation in Lean 4 for the first time. Soundness of the main translation procedure is guaranteed, and experimental results suggest that our algorithm is sufficiently complete to automate the proof of many problems that arise in practical uses of Lean 4. We also find that Lean-auto solves more problems than existing tools on Lean 4's math library Mathlib4.
Problem
Proof automation is crucial to large-scale formal mathematics and verification projects, but Lean 4 lacked a hammer-style tool leveraging automated theorem provers (ATPs) for general-purpose proof automation.
Approach
Lean-auto implements a novel translation algorithm from Lean 4's dependent type theory to ATP logical systems. The translation provides soundness guarantees for the main procedure and enables general-purpose ATP-based proof automation in Lean 4 for the first time. The system combines encoding-based translation with monomorphization and quantifier instantiation to handle Lean 4's type system.
Results
Lean-auto solves more problems than existing tools on Lean 4's math library Mathlib4. Experimental results suggest the algorithm is sufficiently complete to automate proofs of many problems arising in practical uses of Lean 4.
