betaFeedback

WorksComputer Science

crush: Extensible Proof Automation for Lean

Abstract

Lean's rich expressiveness supports higher-order functions, inductive datatypes, and user-defined abstractions, making it challenging to translate proof obligations into first-order Satisfiability Modulo Theory (SMT) queries and reconstruct kernel checked proofs. We present crush, an extensible SMT-backed proof automation framework for Lean. To bridge the gap between Lean's higher-order constructs and the solver's first-order logic, crush uses defunctionalization to encode function values and their applications. We formalize this translation for a supported higher-order fragment and prove its soundness. Moreover, crush provides metaprogramming interfaces for extending both Lean-to-SMT translation and the reconstruction of Lean proofs from solver certificates without modifying the translation pipeline. We implement crush as both a tactic and a backend for other third-party automation systems. We show that across four such use cases that target verification and general proof automation, crush discharges more obligations than the competing backends and reconstructs more kernel-checked proofs than the baselines.

Introduction

Theorem proving has been widely applied in verification of hardware designs [8, 16, 30], software codebases [1, 17, 19] and cloud services [7, 15, 33]. The success of theorem proving in these domains can be attributed to rigorous improvements along two lines: interactive theorem proving and automated theorem provers (ATP). Interactive theorem proving involves manual formalization and proofs, checked by a proof assistant (PA) such as Rocq [34], Lean [23], Isabelle/HOL [24] and Agda [25]. These tools provide rich type systems in which users can formalize properties with abstract and higher-order constructs. On the other hand, automated theorem provers such as Z3 [11], CVC5 [3], and E-Prover [31] support less expressive logics but offer significant automation in proof search.

Integrating ATPs with proof assistants, as in CoqHammer [10] and SMTCoq [2], combines automated search with kernel-checked proofs. While offering merits from both PA and ATP, these integrations face two main challenges, shown in Table 1: (1) translating expressive proof obligations into the solver’s first-order logic and (2) reconstructing kernel-checkable proofs from solvers’ outputs. The translation has to accommodate features like polymorphism and higher-order constructs admitted by PAs and provide extensible encodings that allow users to customize how new definitions are translated. Proof reconstruction has to produce kernel-checkable derivations from certificates generated by the solvers, which may provide only selected premises (i.e., unsat cores), or rely on solver inference rules that have to be mapped into the PA’s proof system.

Table 1: Qualitative comparison of goal translation and proof reconstruction. Poly. shows support of polymorphic premises; HO shows support of higher-order functions; Ext. encoding denotes interfaces for custom encodings. Core-guided and Replay shows whether the tool supports reconstructing ITP-checked proofs from solver certificates (unsat cores and solver-produced proofs, respectively).

ITPToolPoly.HOExt. encodingCore-guidedReplay
Isabelle/HOLsmt [6]✓✓✓×✓
RocqSMTCoq [2]××✓×✓
CoqHammer [10]✓✓×✓×
Leanlean-auto [28]*✓××××
LeanHammer [36]**✓✓×✓×
lean-smt [21]✓×✓×✓
crush✓✓✓✓✓

*SMT backend of lean-auto. **Duper backend of LeanHammer; its replay support is provided separately by lean-smt.

Table 1.

In Lean specifically, proof automation that leverages power of ATPs follows two broad approaches. The first consists of tactics implemented natively in Lean, represented by grind [22] and aesop [20]. These tactics operate directly on Lean expressions and construct proof terms that are checked by the Lean kernel. grind combines congruence closure, E-matching, constraint propagation, case analysis, and specialized solvers for domains such as linear arithmetic and commutative rings. aesop, in contrast, constructs a best-first proof-search tree from an extensible set of rules. Rules may be built from theorem applications, constructor introduction, term rewriting, or arbitrary tactics. These tactics are native to Lean, but their automation is limited to the search procedures, registered rules, and decision procedures implemented within Lean.

The second category consists of hammer-style tactics, such as lean-auto [28] and lean-smt [21]. These tactics collect local hypotheses and the negated proof goal, translate the supported fragment of Lean into a solver language such as SMT-LIB [4], and invoke an external SMT solver. This architecture allows Lean to benefit from mature decision procedures and proof-search heuristics developed for ATPs. When the SMT solver reports unsatisfiability (UNSAT), this fact could either be trusted directly, or be witnessed by a reconstructed proof, using solver’s certificates, that is subsequently and independently checked by the Lean kernel. The translation boundary of existing approaches suffers from a limitation: Lean constructs, including higher-order functions and user-defined abstractions, must be represented in the solver’s supported logic. The applicability and soundness guarantees of these tactics are therefore limited by the coverage and extensibility of both the translation and proof reconstruction procedures.

To address these gaps, we have developed crush, an SMT-backed proof automation framework that combines translation support for higher-order functions with user-extensible encodings, and supports both unsat core-guided proof reconstruction and proof replay from solver inference steps. Users can customize how their definitions are encoded and how the resulting solver proofs are reconstructed in Lean. Our design has three key capabilities. First, crush supports nondependent higher-order functions, including function-valued arguments, partial applications, and lambda abstractions. Through defunctionalization, it represents these functions as values of uninterpreted SMT sorts and introduces application symbols and equations describing their behavior. We formalize this translation and prove its soundness. Second, we provide an extensible translation interface that allows users to define customized encodings of Lean types, functions, and operators without modifying the core translator. Third, we provide an extensible proof replay interface that allows users to define proof reconstruction procedures in the form of typed rewrite rules for terms introduced by their custom translation and for solver’s inference rules, yielding kernel-checkable proofs.

We evaluate crush on four benchmark suites: a Curated set of proof obligations developed by us, Cashmere [14, 18], Velvet [13], and PLean [26]. These include 754 verification conditions (VCs) that contain mixed theories. crush discharges 709 (94.0%) of the 754 VCs, with 693 (91.9%) successfully reconstructed kernel-checked proofs. In comparison, auto, the strongest non-proof-producing tactic, closes only 622 (82.5%), and grind, the strongest proof-producing tactic, closes 641 (85.0%). With kernel-checked proofs, crush also exceeds lean-smt [21] and Duper [9] by 34.7 and 37.1 percentage points in overall coverage, respectively. In summary, our contributions are:

_Extensible translation._ We design a pattern-based interface for extending SMT encodings of Lean types and terms. These extensions combine with translation of higher-order constructs with defunctionalization without modifying the core translator. We also formalized soundness of the defunctionalization pass.

_Extensible proof replay._ We design interfaces for interpreting terms in SMT solver proofs and reconstructing their inference steps in Lean. Users can extend the procedure to support custom encodings and additional solver inference rules.

_The crush framework._ We implement these ideas as a proof automation framework crush in Lean. crush is publicly available on GitHub1.

Overview

Figure 1 summarizes the end-to-end crush pipeline. Given a Lean goal, its hypotheses, and lemmas, crush first prepares a set of propositions by negating the goal, collecting all local hypotheses, and adding user-supplied lemmas. The pre-process pass performs normalization, monomorphization and a bounded quantifier instantiation on the collected formulas. Appendix A describes these standard pre-processing steps in more detail. crush then translates processed formulas into an SMT query, where hypotheses and lemmas are conjoined with the negated goal, and employs defunctionalization to encode higher-order functions and their applications in first-order logic. If the solver reports UNSAT, crush can either trust the solver or construct a Lean proof from an unsat core or by replaying the inference steps produced by the solver. If solver reports SAT (with a model) or Unknown, the user may leverage external tools to fix or refine the proof.

Figure 1. The crush pipeline.

Running Example

Figure 2 defines a function NAND over two bitvectors x,yx, y (with width 4), and states a property for crush to prove. The hypothesis on line 7 specifies that applying run on function f with x gives the result of applying f on x. The function on line 9 applies a mask to a given input yy. Its two inner NAND applications produce the same complemented conjunction; the outer NAND recovers the conjunction of the input and mask. Thus, the left-hand-side application computes the masked input.

The running example: a callback that applies a bitvector mask

Figure 2. The running example: a callback that applies a bitvector mask.

def Nand (x y : BitVec 4) : BitVec 4 :=
  ~~~(x &&& y)

theorem computes_masked
    (run : (BitVec 4 → BitVec 4) →
      BitVec 4 → BitVec 4)
    (hrun : ∀ f x, run f x = f x)
    (x mask : BitVec 4) :
    run (fun y => Nand (Nand y mask)
                       (Nand y mask)) x =
      x &&& mask := by
  crush

Extensible Translation

crush supports extensible translation via rewrite rules to define SMT encodings for Lean terms. Figure 3 shows an example encoding for Nand: the pattern on line 2 matches applications of Nand. The sub-patterns (term x) and (term y) match the arguments and bind the translated results to x and y. The right hand side pattern (line 3) defines the emitted SMT encoding that applies the solver’s bvnand operation with x and y, written in a DSL of an SMT-LIB subset embedded in Lean. § 3 discusses this interface in more detail.

A custom encoding from Nand to solver’s bvnand

Figure 3. A custom encoding from Nand to solver’s bvnand.

Higher-Order Functions

The translation is defined for bitvector operations, but the higher-order function must also be represented in first-order SMT. To encode function values in first-order SMT, crush introduces a fresh first-order sort for each function type and a fresh operator for its application. Then, it emits axioms that assign interpretations to the sort with respect to its definition in Lean. This defunctionalization combines with the extensible translation to encode higher-order functions and bitvector operations into theories supported by the solver. § 4 presents the encoding in detail and proves its soundness.

Extensible Proof Reconstruction

The resulting query can now be handled by an SMT solver. If it is unsatisfiable, crush supports two paths to obtain a kernel-checked proof. Reconstruction from an unsat core selects the relevant Lean hypotheses and uses Lean automation tactics (e.g., grind, omega) to rederive a proof. Alternatively, crush can replay inference steps produced by the solver. crush currently supports the Alethe format [32]. As an inverse of Lean-to-SMT translation, crush also supports extensible proof reconstruction via rewrite rules that map solver inference steps to a Lean term or proof.

Figure 4 shows a rewrite rule for the running example: the pattern on lines 2–3 matches applications of bvnand operation and its arguments. The sub-patterns (e.g., (term x : BitVec _)) on the arguments match bitvectors of arbitrary known widths. On the right hand side (line 4), the pattern defines the translated Lean term. Finally, lines 7–9 configure crush to enable proof reconstruction from Alethe scripts. § 5 discusses the reconstruction procedures and the replay extension interface in detail.

Extending proof replay and selecting Alethe reconstruction

Figure 4. Extending proof replay and selecting Alethe reconstruction.

Extensible Lean-to-SMT Translation

crush provides extensible translation from Lean terms and types to SMT terms and sorts: unfolding a definition exposes the defining equation encoded in the SMT query. Additionally, users may define custom encoding of terms and types as rewrite rules that match head symbols of a term or type application.

Definition Unfolding

The crush_unfold attribute makes the defining equations of a function available whenever that function is called. Figure 5 shows an example of an integer clamp: the annotation on line 1 directs crush to include the definition of clamp in the emitted query. Then, the SMT solver proves the goal by the hypothesis on line 7 and the definition of clamp.

Definition unfolding on functions
@[crush_unfold]
def clamp (x lo hi : Int) : Int :=
  if x < lo then lo
  else if hi < x then hi else x

theorem clamp_bounds (x lo hi : Int)
    (h : lo ≤ hi) :
    lo ≤ clamp x lo hi ∧
      clamp x lo hi ≤ hi := by
  crush

Figure 5. Definition unfolding on functions.

Head- and Type-Indexed Term Translation

Let e♭e^{\flat} denote the SMT term produced from a Lean expression ee, and τ♭\tau^{\flat} denote the SMT sort used to represent a Lean type τ\tau.

Head-indexed translation. Translations on Lean terms can be defined as rewrite rules that match the head of an application. For example, in Figure 3, the pattern on line 2 matches applications of Nand and translates its two operands, producing (Nand⁡ x y)♭=bvnand⁡(x♭,y♭)(\operatorname{Nand}\ x\ y)^{\flat} = \operatorname{bvnand}(x^{\flat}, y^{\flat}).

Type-indexed translation. Rewrites can also be grouped based on the type of Lean terms. For instance, in Figure 6, the Bool pattern on line 2 matches both Bool.not and Bool.xor. The handler then distinguishes these operations by their application heads and arguments. Lines 4 and 6 recursively translate the operands of negation and exclusive-or and construct the corresponding SMT terms. Line 8 ignores other Boolean terms, and the translation procedure will try other rewrite rules if the triggered rule returns none.

Grouping Boolean operations in a type-indexed lowering
register_lowering result-type with ctx <<
  Bool => do
    match ctx.fn, ctx.args with
    | .const ``Bool.not _, #[p] =>
        return some (smt| (not $(← ctx.emitTerm p)))
    | .const ``Bool.xor _, #[p, q] =>
        return some (smt| (xor $(← ctx.emitTerm p) $(← ctx.emitTerm q)))
    | _, _ => return none
>>

Figure 6. Grouping Boolean operations in a type-indexed lowering.

Coordinating Sort and Term Translation

When users define custom types τ\tau in Lean, crush has to handle translations for both terms with type τ\tau and the encoding of τ\tau. With the extensible interface, crush allows users to define rewrite rules over type applications to define encodings for user-defined Lean types.

For example, suppose the user defines a Lean type TotalMap κ\kappa ν\nu, whose values map keys of type κ\kappa to values of type ν\nu. Figure 7 shows the custom encoding of TotalMap κ\kappa ν\nu into the Array sort in SMT. The semantics of rewrite rules over Lean types is similar to rewrite rules over Lean terms. The left-hand-side pattern on line 2 matches the key and value types, and the right-hand-side pattern on line 3 defines the corresponding SMT encoding. Additionally, rewrite rules on lines 7 and 12 define encodings for applications of get and set functions associated with TotalMap, translating get to select and set to store.

Encoding of TotalMap

Figure 7. Encoding of TotalMap.

crush performs sort-checking on queries emitted by handlers before invoking the solver. This light-weight checking catches incompatible sort and term translations, such as erroneously applying an array operation (e.g., select) to an integer. However, crush does not check that the SMT encoding is semantically correct: the user is responsible for ensuring the correctness of extended translations. For this example, since TotalMap is encoded as SMT Arrays, the user should ensure that TotalMap.get and TotalMap.set are consistent with the axioms of the array theory (i.e., get(set(mm, kk, vv), kk) = vv).

Higher-Order Translation via Defunctionalization

crush uses defunctionalization to encode higher-order functions in first-order SMT, introducing uninterpreted sorts for function types and replacing function values and their applications with uninterpreted symbols constrained by axioms. Our translation procedure supports the encoding for a subset of Lean with monomorphic, nondependent higher-order constructs. We model this translation procedure in Lean and formalize its soundness.

Defunctionalization

Function values and application. For a nondependent function type θ=σ1→⋯→σn→τ\theta= \sigma_1 \to\cdots\to\sigma_n \to\tau, where τ\tau is not a function type, crush introduces an uninterpreted sort FnθFn_\theta whose elements represent function values. We refer to these uninterpreted sorts as Fn sorts. Its application symbol has signature

app⁡θ:Fnθ×σ1b×⋯×σnb→τb\operatorname{app}_\theta: Fn_\theta\times\sigma_1^b \times\cdots\times\sigma_n^b \to\tau^b

An application f a1⋯anf\ a_1 \cdots a_n becomes app⁡θ(f,a1b,…,anb)\operatorname{app}_\theta(f, a_1^b, \ldots, a_n^b), where ff is a function symbol. Quantification over a function therefore becomes ordinary first-order quantification over the corresponding uninterpreted sort Fn.

Lambdas and captured variables. For each lambda ℓ=λx1⋯xn. e\ell= \lambda x_1 \cdots x_n.\ e, crush introduces a fresh uninterpreted symbol clos⁡ℓ\operatorname{clos}_\ell of sort FnθℓFn_{\theta_\ell}. Then, crush generates an axiom about the closure application according to its definition, where yˉ\bar{y} are variables captured by ℓ\ell:

∀yˉ, xˉ.app⁡θ(clos⁡ℓ(yˉ),xˉ)=eb\forall\bar{y},\ \bar{x}.\quad\operatorname{app}_\theta(\operatorname{clos}_\ell(\bar{y}), \bar{x}) = e^b

Here the variables xˉ,yˉ\bar{x}, \bar{y} range over their translated sorts, and the body is translated under the same bindings. The closure symbol clos⁡ℓ\operatorname{clos}_\ell is uninterpreted, and its semantics are axiomatized according to its definition.

Partial application and function equality. crush applies η\eta-expansion2 to partial applications, transforming them into closures. Then, it reuses the encoding for lambdas to encode the η\eta-expanded terms. When the query compares function values for equality, crush additionally emits an extensionality axiom for the corresponding Fn sort.

Guarded Sub-types. For types represented by a subset of an SMT sort, such as Nat within Int, the encoding represents inhabitants of the Lean types and constrains the application results accordingly. For example, crush reuses SMT solver’s integer theory to represent Nat, and for each query involving a Nat xx, the assertion will be guarded by x≥0x \ge0.

Encoding the running example. Let B denote the SMT sort of BitVec 4 and θ=BitVec 4→BitVec 4\theta= \mathrm{BitVec}\ 4 \to\mathrm{BitVec}\ 4. The application symbol has signature app⁡θ:Fnθ×B→B\operatorname{app}_\theta: Fn_\theta\times B \to B. For the fixed mask mm in Figure 2, the closure on line 9, denoted by ℓ\ell, is represented by the nullary closure symbol clos⁡ℓ:Fnθ\operatorname{clos}_\ell: Fn_\theta. Combining the closure body with the custom translation in Figure 3 gives

∀y:B.app⁡θ(clos⁡ℓ,y)=bvnand⁡(bvnand⁡(y,m),bvnand⁡(y,m))\forall y : B.\quad\operatorname{app}_\theta(\operatorname{clos}_\ell, y) = \operatorname{bvnand}(\operatorname{bvnand}(y,m), \operatorname{bvnand}(y,m))

The run function on line 5 becomes an uninterpreted symbol run⁡^:Fnθ×B→B\widehat{\operatorname{run}} : Fn_\theta\times B \to B. Its hypothesis and the negated goal become, respectively,

∀f:Fnθ, y:B.run⁡^(f,y)=app⁡θ(f,y),run⁡^(clos⁡ℓ,x)≠bvand⁡(x,m)\forall f : Fn_\theta,\ y : B.\quad\widehat{\operatorname{run}}(f,y) = \operatorname{app}_\theta(f,y), \qquad \widehat{\operatorname{run}}(\operatorname{clos}_\ell,x) \ne\operatorname{bvand}(x,m)

Instantiating the hypothesis with clos⁡ℓ\operatorname{clos}_\ell and xx, and the closure equation with xx completes the proof by contradiction.

Soundness of Defunctionalization

In this section, we describe the formalization of the defunctionalization pass and show the proof skeleton of its soundness. Full formalization in Lean is available in our artifact3. We first formalize the higher-order (HO) and first-order (FO) languages shown on the left and right of Figure 8, respectively. Both languages have Boolean literals, equality, logical connectives, and quantifiers. HO models the fragment of Lean supported by this transformation. In HO, β\beta ranges over base (non-arrow) sorts, σ\sigma, τ\tau over HO sorts, ee over terms, and cc over typed constants. FO uses FO sorts ss (including the same base sorts β\beta as HO) and terms tt, replacing each HO function sort θ\theta by Fnθ\mathrm{Fn}_{\theta} as described earlier. The symbols kk are uncurried constant symbols c^\hat{c}, application symbols appθ\mathrm{app}_{\theta}, and closure symbols closℓ\mathrm{clos}_{\ell}. Each has type s1×⋯×sn→ss_1 \times\cdots\times s_n \to s and is fully applied, with n=0n = 0 for nullary symbols. θ=σ1→⋯→σn→τ,τ∈{Bool,β}.\theta= \sigma_1 \to\cdots\to\sigma_n \to\tau,\quad\tau\in\{\mathrm{Bool},\beta\}.

HO syntax (left), FO syntax (right), and their denotational semantics

Figure 8. HO syntax (left), FO syntax (right), and their denotational semantics.

Function application

f:θai:σiF(ai)=(ai♭,Cai,Eai)(1≤i≤n)F(f a1⋯an)=(app⁡θ(f,aˉ),⋃iCai,⋃iEai)\begin{aligned} f &: \theta\qquad a_i : \sigma_i \qquad\mathcal{F}(a_i) = (a_i^{\flat}, C_{a_i}, E_{a_i}) \quad(1 \le i \le n)\\ \mathcal{F}(f\ a_1 \cdots a_n) &= (\operatorname{app}_{\theta}(f,\bar{a}), \bigcup_i C_{a_i}, \bigcup_i E_{a_i}) \end{aligned}

Closure construction

ℓ=λxˉ.e:θe:τyˉ=FV⁡(ℓ)F(e)=(e♭,Ce,Ee)F(ℓ)=(clos⁡ℓ(yˉ),Ce∪{Kℓ},Ee)Kℓ=(∀yˉ,xˉ. app⁡θ(clos⁡ℓ(yˉ),xˉ)=e♭).\begin{aligned} \ell&= \lambda\bar{x}.e : \theta\qquad e : \tau\qquad\bar{y} = \operatorname{FV}(\ell)\\ \mathcal{F}(e) &= (e^{\flat},C_e,E_e)\\ \mathcal{F}(\ell) &= (\operatorname{clos}_{\ell}(\bar{y}), C_e \cup\{K_{\ell}\}, E_e)\\ K_{\ell} &= (\forall\bar{y},\bar{x}.\ \operatorname{app}_{\theta}(\operatorname{clos}_{\ell}(\bar{y}),\bar{x}) = e^{\flat}). \end{aligned}

Function equality

u,v:θF(u)=(u♭,Cu,Eu)F(v)=(v♭,Cv,Ev)F(u=v)=(u♭=v♭,Cu∪Cv,Eu∪Ev∪{ext⁡θ})ext⁡θ=(∀f,g:Fnθ. (∀xˉ. app⁡θ(f,xˉ)=app⁡θ(g,xˉ))→f=g).\begin{aligned} u,v &: \theta\qquad\mathcal{F}(u) = (u^{\flat},C_u,E_u) \qquad\mathcal{F}(v) = (v^{\flat},C_v,E_v)\\ \mathcal{F}(u=v) &= (u^{\flat}=v^{\flat}, C_u\cup C_v, E_u\cup E_v\cup\{\operatorname{ext}_{\theta}\})\\ \operatorname{ext}_{\theta} &= (\forall f,g:\mathrm{Fn}_{\theta}.\ (\forall\bar{x}.\ \operatorname{app}_{\theta}(f,\bar{x})=\operatorname{app}_{\theta}(g,\bar{x})) \to f=g). \end{aligned}

Definition 1 (Denotation and satisfaction). Let II be a model of either HO or FO. We write ⟦α⟧I\llbracket\alpha\rrbracket_I for the carrier of sort α\alpha, i.e., the set of values interpreting α\alpha in model II. We write ⟦u⟧I(ρ)\llbracket u \rrbracket_I(\rho) for the denotation of term uu in model II under valuation ρ\rho. We use ∅\varnothing to denote an empty valuation. For a collection TT of closed formulas in the corresponding language, define

I⊨T  ⟺  ∀φ∈T. ⟦φ⟧I(∅).I \models T \iff\forall\varphi\in T.\ \llbracket\varphi\rrbracket_I(\varnothing).

A higher-order model MM assigns nonempty carriers M(β)M(\beta) to base sorts and values M(c)M(c) to constants; arrow sorts denote full function spaces. A first-order model NN assigns arbitrary nonempty carriers to base sorts and Fn\mathrm{Fn} sorts, and interpretations N(k)N(k) to symbols. For denotational semantics in Figure 8, we write II for a model of either language, u,vu,v for its terms, and α\alpha for a sort in that language. A valuation ρ\rho assigns values to variables. Boolean terms denote Lean propositions (Prop), and quantifiers extend the valuation with a value from the interpretation of their binder sort. The sort encoding τ♭\tau^{\flat} leaves Boolean and base sorts unchanged, with θ♭=Fnθ\theta^{\flat}=\mathrm{Fn}_{\theta} for an HO function sort θ\theta.

Definition 2 (Defunctionalization). Defunctionalization maps a well-typed higher-order term e:τe:\tau to F(e)=(e♭,Ce,Ee)\mathcal{F}(e)=(e^{\flat},C_e,E_e), where e♭:τ♭e^{\flat}:\tau^{\flat} is a first-order term with first-order sort τ♭\tau^{\flat} and Ce,EeC_e,E_e are sets of closed closure equations and extensionality axioms, respectively. Core definitions are given in Figure 9. Complete definitions are shown in Appendix § 10.2.§ 1.

Defunctionalization selected rules

Figure 9. Defunctionalization (selected rules).

In Figure 9, θ\theta has a complete argument list σˉ\bar{\sigma} and non-function result τ\tau. Each aˉi\bar{a}_i is the first-order term returned by the recursive call F(ai)\mathcal{F}(a_i), including defunctionalization when aia_i has function type. Application of a function variable f:θf:\theta passes these terms to app⁡θ\operatorname{app}_{\theta} and accumulates their generated axioms.

For a lambda ℓ=λx. e\ell=\lambda x.\,e, the closure symbol takes its free variables yˉ=FV⁡(ℓ)\bar{y}=\operatorname{FV}(\ell), and KℓK_{\ell} specifies its behavior using the recursively translated non-function body ee. Variables of Fn\mathrm{F}_n sorts, constants, and partial applications are η\eta-expanded over their remaining arguments and use the same closure construction. Appendix § 10.2.§ 1 gives the generalized rule, including lambdas whose bodies still have function type. Equality at function type θ\theta additionally contributes ext⁡θ\operatorname{ext}_{\theta} that encodes functional extensionality. Logical connectives and quantifiers preserve their operators, replacing quantifications to the corresponding first-order sorts.

Definition 3 (First-order encoding). For a finite collection TT of closed higher-order formulas, let (φ♭,Cφ,Eφ)=F(φ)(\varphi^{\flat},C_{\varphi},E_{\varphi})=\mathcal{F}(\varphi) and define

D(T)=⋃φ∈T(Cφ∪Eφ∪{φ♭}).D(T)=\bigcup_{\varphi\in T}\left(C_{\varphi}\cup E_{\varphi}\cup\{\varphi^{\flat}\}\right).

Definition 4 (Canonical model extension). For each lambda ℓ\ell with free variables yˉ=(y1,…,ym)\bar{y}=(y_1,\ldots,y_m), let ρℓ,vˉ\rho_{\ell,\bar{v}} be the valuation defined by ρℓ,vˉ(yi)=vi\rho_{\ell,\bar{v}}(y_i)=v_i for 1≤i≤m1\leq i\leq m. The extension M⋆M^{\star} of MM interprets the generated symbols by

∥Fnθ∥M⋆=∥θ∥M,\lVert\mathrm{F}_n\theta\rVert_{M^{\star}}=\lVert\theta\rVert_M,
M⋆(app⁡θ)(f,aˉ)=f a1⋯an,M^{\star}(\operatorname{app}_{\theta})(f,\bar{a})=f\,a_1\cdots a_n,
M⋆(clos⁡ℓ)(vˉ)=⟦ℓ⟧M(ρℓ,vˉ).M^{\star}(\operatorname{clos}_{\ell})(\bar{v})=\llbracket\ell\rrbracket_M(\rho_{\ell,\bar{v}}).

Since corresponding HO and FO sorts have the same carriers in MM and M⋆M^{\star}, we use ρ\rho for both valuations.

Lemma 1 (Preservation of denotations). For every well-typed higher-order term ee, model MM, and valuation ρ\rho, with M⋆M^{\star} as in Definition 4,

⟦e♭⟧M⋆(ρ)=⟦e⟧M(ρ).\llbracket e^{\flat}\rrbracket_{M^{\star}}(\rho)=\llbracket e\rrbracket_M(\rho).

Proof sketch. We proceed by induction on typed terms. In the lambda case, we use the fact that denotation depends only on free variables, so reconstructing the captured values suffices. The full proof is shown in Appendix § 10.2.§ 3.

Lemma 2 (Validity of generated axioms). For every model MM and well-typed term ee,

M⋆⊨Ce∪Ee.M^{\star}\models C_e\cup E_e.

Proof sketch. We establish closure equations using Definition 4 and Lemma 1. In M⋆M^{\star}, the Fn\mathrm{F}_n sorts are interpreted as function spaces and the application symbols as function application, so the extensionality axioms follow from function extensionality. The full proof appears in Appendix § 10.2.§ 4.

We combine these properties to obtain the following result.

Theorem 1 (Soundness). For every finite collection TT of closed higher-order formulas, if D(T)D(T) is unsatisfiable, then TT is unsatisfiable.

Proof sketch. We argue by contradiction. If M⊨TM \models T, Lemma 1 makes every translated formula true in M⋆M^\star, while Lemma 2 supplies all auxiliary axioms. Thus M⋆⊨D(T)M^\star\models D(T), contradicting its unsatisfiability. The full proof is shown in Appendix § 10.2.§ 5.

Proof Reconstruction

For a goal GG in Lean, crush emits the translated hypotheses and ¬G\lnot G to the solver. When the solver reports SAT, it provides a model of the encoded first-order formula, possibly spurious if an opaque definition was not unfolded; when it reports UNKNOWN, the Lean goal is left unresolved. When it reports UNSAT, the solver may provide an UNSAT core, a proof script, or both. In the UNSAT case, crush attempts to reconstruct a kernel-checked proof through two approaches: use the UNSAT core to select premises and search the proof via tactics in Lean, or replay the solver’s inference steps (proof scripts), translating them into Lean proof terms.

Core-Guided Reconstruction

An UNSAT core contains assertions sufficient for a contradiction, usually much smaller than the input. crush maps them back to Lean hypotheses and searches for a proof by contradiction from the hypotheses and the negated goal leveraging existing proof automation tactics (e.g., omega or grind). Appendix § 10.3 provides details for the search procedure. To extend search procedure, users may mark a theorem as a reconstruction hint via @[crush_reconstruct]. When the current goal matches the conclusion of a marked theorem, it is applied to the goal, and crush proves the premises recursively.

Extensible Solver Inference Replay

Alternatively, crush can replay the proof script generated by SMT solvers to reconstruct kernel-checked Lean proofs. A proof script is a list of inference steps, where each inference step records a conclusion, a rule, and any premises or arguments used by the rule to derive the conclusion. crush relies on rewrite rules to translate terms and inference steps in proof scripts into Lean term and Lean proofs. Users may extend those rewrite rules via crush’s extensible and type-aware interfaces. Appendix § 10.3 provides the details of the replay procedure.

Term decoding. Users may specify translations from SMT operators in proof scripts into Lean terms via register_crush_replay term command. The translated Lean terms are further type-checked by the Lean kernel. As an example, Figure 4 defines a handler for the SMT operator bvand, which requires the arguments to have Lean type BitVec and translates the expression into a complemented conjunction.

Solver inference replay. Users may define translations of inference steps into a Lean proof with register_crush_replay rule command. For example, the left of Figure 10 shows a use of "bv-not-idemp" rewrite rule in the solver’s inference step, which rewrites a SMT term bvnot(bvnot(a)) into a and asserts its equality. The right of Figure 10 registers a rule to translate "bv-not-idemp" in the proof script into a Lean proof of ∼(∼x)=x\sim(\sim x) = x (where ∼\sim denotes bitwise complement in Lean), using the existing lemma BitVec.not_not.

Alethe inference and Lean inference handler

Figure 10. An inference from the running example’s certificate and a replay handler.

Current limitations. The proof replay procedures in crush rely on the SMT solver’s ability to produce a proof script. For CVC5, its Alethe proof generation does not cover all theories it can solve. Moreover, the built-in rules in crush’s replay procedures may not cover every SMT encoding or inference step. In practice, these gaps can be filled by additional user-supplied rules.

Evaluation

We compare crush against related proof automation frameworks on metrics for verification coverage, runtime, and proof reconstruction. We first compare overall coverage and runtime (§6.1) for each benchmark suite, and then compare crush pair-wise with each baseline framework on the VCs solved by both (§6.2). Finally, we examine how core-guided reconstruction and solver inference replay contribute to obtaining kernel-checked proofs (§6.3).

Experimental setup. The benchmark comprises 754 VCs from four suites: Curated (20), Cashmere [18] (38), Velvet [13] (504), and PLean [26] (192). We compare crush with lean-auto (auto) [28], Duper [9], lean-smt [21], and Grind (grind) [22]. Curated is a standalone collection of Lean goals developed by us, covering higher-order functions, datatypes, arithmetic, bitvectors, and strings. Cashmere, Velvet and PLean use Loom [14] in their VC generation. Cashmere and Velvet are case studies of Loom, covering VCs from program verification. PLean covers verification of distributed protocols written in P [12] language embedded in Lean. We plug crush and the baselines into Loom as SMT backends to discharge the generated VCs. We evaluate crush both with SMT trusted (i.e., without proof reconstruction) and with kernel-checked proof reconstruction. The former trusts the solver’s verdict and, like auto, uses an axiom to close the goal.

The latter requires a kernel-checked proof of the original goal and combines core-guided reconstruction with replay of the solver’s inference steps recorded in the Alethe proof format (Alethe replay). In this case, crush is considered successful if it produces a kernel-checked proof for the original goal.

All experiments ran on an Apple M1 Pro CPU with 32 GB of memory. We use cvc5 1.3.4 as the SMT backend. We use Duper revision ca7c5862, lean-smt revision e5025665, and Lean 4.32.2 (except for auto on Cashmere, Velvet, and PLean, for which we retain Lean 4.24.0 to preserve the existing Loom–lean-auto integration). We set a limit of 5 seconds on each solver call and a limit of 1M Lean heartbeats on each tactic invocation. We measure the time for each tactic on each VC, including translation, solver execution, and proof reconstruction.

Verification Coverage and Runtime

Figure 11 shows the number of VCs discharged within each time threshold per VC. Here, the x-axis shows the time threshold in seconds for each VC on a log scale; the y-axis shows the number of VCs discharged within that time threshold. The dashed horizontal line marks the total number of VCs in each benchmark suite.

Figure 11. Verification coverage against time per VC.

Across the four benchmarks, crush discharges 709 VCs (94.0%) when trusting the solver’s results, and 693 (91.9%) when enabling proof reconstruction. Among the compared baselines, grind achieves the highest coverage (641 VCs), followed by auto (622), lean-smt (431), and Duper (413). Notably, crush achieves the highest overall coverage even when kernel-checked proofs are required. The runtime curves show a tradeoff: grind discharges many VCs at shorter time thresholds, while crush achieves higher overall coverage. The advantage also varies by benchmark suites. On PLean, auto discharges more VCs than kernel-checked crush (172 versus 164), although trusted crush discharges 174.

Pairwise Comparison with crush

Table 2 compares crush (with proof reconstruction) against each baseline on the same VCs. Runtimes are reported as mean ±\pm standard deviation over VCs discharged by both tools. crush discharges more VCs in all pairs except against auto on PLean. The trusted-mode comparison is in Table 5, Appendix § 10.4.

BenchmarkBaselinecrush onlyBaseline onlyBothcrushBaseline
Curated (20 VCs)auto2017365.0±298.1365.0 \pm298.1322.2±20.1322.2 \pm20.1
Duper8111313.1±191.1313.1 \pm191.198.3±24.198.3 \pm24.1
lean-smt7012404.2±338.6404.2 \pm338.6106.8±31.5106.8 \pm31.5
grind3016371.4±309.3371.4 \pm309.35.5±4.85.5 \pm4.8
Cashmere [18] (38 VCs)auto20018235.9±395.8235.9 \pm395.8294.0±36.0294.0 \pm36.0
Duper17021252.9±407.1252.9 \pm407.1109.3±102.6109.3 \pm102.6
lean-smt21017156.5±352.4156.5 \pm352.4135.6±44.2135.6 \pm44.2
grind19019223.6±388.4223.6 \pm388.49.8±2.79.8 \pm2.7
Velvet [13] (504 VCs)auto7013402598.5±1400.7598.5 \pm1400.7372.5±215.2372.5 \pm215.2
Duper1843288287.0±483.2287.0 \pm483.2220.3±517.4220.3 \pm517.4
lean-smt18010292611.4±1584.3611.4 \pm1584.3142.1±95.9142.1 \pm95.9
grind379435460.8±595.6460.8 \pm595.626.1±26.826.1 \pm26.8
PLean [26] (192 VCs)auto2101624517.8±14086.14517.8 \pm14086.13380.3±5970.03380.3 \pm5970.0
Duper75089644.6±284.3644.6 \pm284.32755.4±8169.22755.4 \pm8169.2
lean-smt651991611.3±9096.71611.3 \pm9096.71303.1±3731.41303.1 \pm3731.4
grind201624493.5±14089.64493.5 \pm14089.61206.5±2327.61206.5 \pm2327.6

Table 2. Head-to-head comparison with crush using proof reconstruction. Times are mean ±\pm standard deviation across VCs discharged by both tools, after averaging repetitions per VC.

BenchmarkBaseline# VCs Discharged: crush only# VCs Discharged: Baseline only# VCs Discharged: BothTime on Both (ms): crushTime on Both (ms): Baseline
Curated (20 VCs)auto2017234.8±108.3234.8 \pm108.3322.2±20.1322.2 \pm20.1
Curated (20 VCs)Duper8111234.1±114.0234.1 \pm114.098.3±24.198.3 \pm24.1
Curated (20 VCs)lean-smt7012239.4±106.9239.4 \pm106.9106.8±31.5106.8 \pm31.5
Curated (20 VCs)grind3016234.6±112.8234.6 \pm112.85.5±4.85.5 \pm4.8
Cashmere (38 VCs)auto20018227.2±381.8227.2 \pm381.8294.0±36.0294.0 \pm36.0
Cashmere (38 VCs)Duper17021247.0±400.5247.0 \pm400.5109.3±102.6109.3 \pm102.6
Cashmere (38 VCs)lean-smt21017151.4±341.1151.4 \pm341.1135.6±44.2135.6 \pm44.2
Cashmere (38 VCs)grind19019215.4±374.6215.4 \pm374.69.8±2.79.8 \pm2.7
Velvet (504 VCs)auto7310405398.3±490.2398.3 \pm490.2378.6±225.7378.6 \pm225.7
Velvet (504 VCs)Duper1903288232.0±345.8232.0 \pm345.8220.3±517.4220.3 \pm517.4
Velvet (504 VCs)lean-smt1859293377.8±480.7377.8 \pm480.7145.5±112.5145.5 \pm112.5
Velvet (504 VCs)grind439435349.5±371.7349.5 \pm371.726.1±26.826.1 \pm26.8
PLean (192 VCs)auto201723583.1±11750.43583.1 \pm11750.43621.0±5972.53621.0 \pm5972.5
PLean (192 VCs)Duper85089609.6±268.2609.6 \pm268.22755.4±8169.22755.4 \pm8169.2
PLean (192 VCs)lean-smt7401001521.8±8680.91521.8 \pm8680.91298.7±3712.71298.7 \pm3712.7
PLean (192 VCs)grind1201623528.6±12102.23528.6 \pm12102.21206.5±2327.61206.5 \pm2327.6

Table 5. Head-to-head comparison with crush, trusting SMT verdicts. Times are mean ±\pm standard deviation across VCs discharged by both tools, after averaging repetitions per VC.

The pairwise results show that crush can prove many obligations missed by the baselines. Across the four suites, crush proves 61 VCs that grind cannot close, while grind proves 9 that crush cannot close. On Velvet, crush proves 184 VCs missed by Duper and 180 missed by lean-smt; these baselines prove only 3 and 10 VCs, respectively, that crush misses. On VCs solved by both tools, crush has a higher mean runtime in most comparisons, and grind is faster on all four suites. The tradeoff varies by workload: on PLean, crush is slower on average than lean-smt (1611.3 versus 1303.1 ms) on the 99 VCs, but it also proves 65 VCs that lean-smt misses.

MethodFailure modeVCs
Alethe replayCertificate generation431
Alethe replayTerm decoding1
Alethe replayTotal432 / 503
CombinedCertificate generation and core-guided reconstruction11
CombinedLean heartbeat limit2
CombinedTactic failure during replay3
CombinedTotal16 / 503

Table 3. Proof reconstruction failures among VCs discharged by SMT.

We observe that reconstruction failures mainly arise when cvc5 cannot produce a proof script and core-guided reconstruction also fails to recover a proof. We examine these cases in more detail in the next section.

Proof Reconstruction

We evaluate how combining Alethe replay with core-guided reconstruction affects proof coverage, examine the remaining failure modes, and report the manual effort needed to define replay handlers.

Reconstruction coverage. Figure 12 shows the number of VCs that have proofs reconstructed by crush and lean-smt in each case study, with the same x- and y-axes as in Figure 11. In total, crush closes 693 VCs when combining Alethe replay with core-guided reconstruction, compared with 241 using Alethe replay alone and 431 for lean-smt. Adding core-guided reconstruction therefore enables crush to close more VCs.

Figure 12. Kernel-checked proof reconstruction coverage over time per VC.

Failure analysis for Alethe replay. We further categorized the failure modes to identify specific limitations in the Alethe replay, and which limitations were overcome by core-guided reconstruction. Solver certificate generation caused 431 of the replay failures among the 503 VCs discharged by SMT. Although cvc5 concludes unsatisfiability, it does not fully support proof generation in Alethe. For example, it currently cannot generate a proof for the theory of arrays, which is used in the Cashmere and Velvet suites. Here, core-guided reconstruction often allows crush to obtain kernel-checked proofs even when the solver’s proof-generation support is insufficient. The other replay failure stems from a choice expression in the certificate, which chooses an element from a set. crush does not currently support decoding this expression, since it would require synthesizing a proof of non-emptiness of the set from which the element is chosen.

In 11 VCs, certificate generation fails and core-guided reconstruction also fails to find a proof: 4 occur in Velvet and 7 in PLean. The remaining failures are due to exhausted heartbeat budgets and tactic failures, caused by insufficient lemmas for the built-in proof search procedures during replay.

Replay implementation effort. The built-in replay handler library covers assumption normalization, logic and equality, quantifiers, arithmetic, bitvectors, and strings through the extension interface (§ 5.2). The 55 manually defined handlers take 256 LoC, with another 797 LoC of supporting lemmas, for a total of 1,053 LoC (Table 4).

CategoryHandlersHandler LoCLemma LoCTotal
Assumption normalization2163450
Logic and equality10471057
Quantifiers132225
Arithmetic1768311379
Bitvectors1372337409
Strings125083133
Total552567971,053

Table 4. Implementation size of built-in Alethe replay extensions.

Related Work

ATP Integration in Proof Assistants. CoqHammer [10] translates Rocq goals through CIC₀ into untyped first-order logic. Although there is a soundness proof for CoqHammer’s core encoding, its implementation uses approximations that can compromise soundness, including omitted type guards in lambda-lifting equations. It ensures soundness by reconstructing kernel-checked Rocq proofs using ATP-selected premises. crush instead mechanizes the soundness of defunctionalization for its supported higher-order fragment.

SMTCoq [2] reifies Rocq goals into SMT formulas and validates solver certificates using a verified checker. Its modular architecture supports additional solvers and theories; it provides extensible preprocessing through Trakt [5]. It targets universal goals over supported SMT theories. In contrast, crush supports higher-order terms and existential quantifications, and natively provides extensible translation and proof replay. Its handlers construct kernel-checked Lean proofs without requiring separate soundness proofs for their implementations.

Automation Tactics in Lean. Several prior works attempted to close the gap between Lean and SMT solvers for better proof automation. lean-auto [28] uses a monomorphization pass to translate dependent type theory into higher-order logic, but its SMT backend supports a restricted first-order fragment without SMT proof reconstruction or custom encoding interfaces. lean-smt [21] uses lean-auto for monomorphization and provides extensible SMT translation, term decoding, and inference replay. Its translation similarly requires a supported first-order fragment. LeanHammer [36] combines premise selection, lean-auto’s higher-order translation, Zipperposition [35] proof search, and Duper [9] reconstruction from selected premises. More recent versions also integrate lean-smt, hence inheriting its SMT translation and replay capabilities.

crush is also broadly related to tactics that are natively implemented in Lean. Grind [22] implements several SMT solving procedures in Lean to perform proof search; Duper [9] implements proof-producing superposition, similar to Isabelle’s Metis [27]; Aesop [20] implements white-box proof search in Lean.

Conclusion and Future Work

We present crush, an extensible proof automation framework for Lean. It provides extensible translation interfaces for encoding Lean proof obligations into first-order SMT and leverages defunctionalization to support higher-order constructs. We have also provided a soundness proof of this translation procedure for the supported fragment of Lean. crush reconstructs proofs from solver certificates and supports proof search guided by unsat cores and replaying inference steps produced by proof-producing SMT solvers. On 4 benchmark suites with 754 verification conditions in Lean, crush solves 709 (94.0%) when trusting the SMT solver and 693 (91.9%) when proof reconstruction is required, outperforming all the baseline approaches.

Future work. We aim to support dependent function types and extend the soundness formalization beyond defunctionalization to Lean-to-SMT-LIB translation. For proof reconstruction, we plan to integrate tactics such as Duper [9], support CPC [29] certificates, and synthesize non-emptiness proofs for choice expressions in solver proof certificates. We also aim to improve the feedback to the user when the SMT solver reports SAT, for example, by distinguishing true and spurious counter-examples.

Data Availability

The implementation of crush, its mechanized proofs, benchmark data, and scripts for reproducing the experiments are publicly available at https://github.com/AD1024/lean-crush/tree/tacas-ae.

Appendix

Details of Pre-processing passes

Given a Lean proof goal, crush first constructs a set of propositions and preprocesses them before translating (defunctionalizing) them.

Fact Collection and Normalization

crush collects the negated goal, local propositional hypotheses, and lemmas supplied explicitly or selected from the environment. It retains their origins so an unsat core can later be mapped back to the corresponding Lean facts.

crush further applies normalization on the collected propositions. If they use definitions that are marked with crush_unfold, crush will rewrite their applications using the definitions’ equation lemmas and also expose these (quantified) equations as facts in future passes. We note that such rewriting is performed by tactics that produce equality proofs checked by Lean kernel. Moreover, crush will not expose equations of unused definitions, preventing introduction of quantifiers and instantiations that are unproductive.

Example. Suppose double(x)double(x) is defined as x+xx+x and marked with crush_unfold. For a goal 0≤double(x)0 \le double(x) under the hypothesis 0≤x0 \le x, fact collection produces

0≤xand¬(0≤double(x)).0 \le x \qquad\text{and} \qquad\neg(0 \le double(x)).

Because the marked definition occurs in the negated goal, normalization rewrites the latter fact to ¬(0≤x+x)\neg(0 \le x+x). The recorded equality proof connects this normalized contradiction back to the original goal.

Lemma Monomorphization

Lean lemmas may be polymorphic, i.e., quantifying over types, whereas SMT symbols have concrete sorts. Translating the type variables of such a lemma into some uninterpreted sorts will make SMT solvers unable to use it for a concrete sort, e.g., Int. crush therefore collects the concrete data types in the proof obligation and specializes the type parameters of polymorphic lemmas at those types, maybe iteratively. Every instance is obtained by applying the original Lean proof. The numbers of instances and iterations are bounded by user-configurable options, which could reduce the completeness but still preserve soundness. We note that function types are handled separately by the defunctionalization procedure in § 4.

Example. Consider a polymorphic function ff and a hypothesis

h:∀(α:Type) (xs:List α), f α xs=0.h : \forall(\alpha: \mathrm{Type})\ (xs : \mathrm{List}\ \alpha),\ f\ \alpha\ xs = 0.

If the goal is f Int ys=0f\ \mathrm{Int}\ ys = 0, where ys:List Intys : \mathrm{List}\ \mathrm{Int}, the occurrences of Int and List Int direct crush to apply hh to Int. The resulting fact

hInt:∀(xs:List Int), f Int xs=0h_{\mathrm{Int}} : \forall(xs : \mathrm{List}\ \mathrm{Int}),\ f\ \mathrm{Int}\ xs = 0

uses the same concrete SMT symbols as the goal while retaining h Inth\ \mathrm{Int} in its Lean proof.

Bounded Quantifier Instantiation

Bounded quantifier instantiation supplies solver-side E-matching with a finite set of relevant ground instances. E-matching requires a suitable ground term before instantiating a quantified proposition, so it can miss a forward chain in which one instance produces the trigger for the next. Therefore, crush applies active bounded instantiation by matching quantified lemmas against ground terms and proposition occurrences already in the query, including newly generated instances. Note that every instance is constructed by applying its quantified Lean proof to the selected arguments.

crush takes a "two-shot" approach after quantifier instantiation. It first emits an SMT query without the quantified lemmas, avoiding unbounded solver-side instantiation. It closes the goal if this query is already UNSAT. If the query is SAT or unknown, crush retries with the complete set of propositions including quantified lemmas.

Example. Let the selected lemmas and goal be

step: ∀x, R x (next x),lift: ∀x y, R x y→P y,goal: ∃y, R a y∧P y.\begin{aligned} \mathit{step} &:\ \forall x,\ R\ x\ (\mathit{next}\ x),\\ \mathit{lift} &:\ \forall x\ y,\ R\ x\ y \to P\ y,\\ \mathit{goal} &:\ \exists y,\ R\ a\ y \land P\ y. \end{aligned}

The ground term aa first instantiates step\mathit{step}, producing R a (next a)R\ a\ (\mathit{next}\ a). That new occurrence fixes both arguments of lift\mathit{lift}, producing P (next a)P\ (\mathit{next}\ a) in the next round. The solver can then choose next a\mathit{next}\ a as the existential witness. Both generated facts carry applications of the original lemmas as Lean proofs.

Formalization of Defunctionalization

We formalize typed higher-order and first-order languages and a translation between them, and prove Theorem 1.

Languages and Translation

Figure 8 defines both languages and their semantics. A higher-order signature assigns a type to each constant, and a context assigns types to local variables. The Lean representation is Intrinsically typed, i.e., indexing terms by their signature, context, and type, so only well-typed terms can be constructed. Formulas have type Bool; they are closed when their local context is empty.

First-order terms are likewise indexed by their context and result sort. Generated symbols are identified by the original constant, function type, or closure they represent, independently of concrete SMT names. Their argument and result sorts are part of their types. Valuations respect these type and sort assignments. In both languages, quantifiers range over the full interpretation of their binder types or sorts, and the valuation is extended with the bound value when evaluating the body.

Recursive translation. The following rules give the full definition of F\mathcal{F}, including the cases summarized in Figure 9. Throughout, τ∈{Bool,β}\tau\in\{\mathrm{Bool},\beta\} is a non-function sort and θ=σ1→⋯→σn→τ\theta= \sigma_1 \to\cdots\to\sigma_n \to\tau with n≥1n \ge1. Variables and constants of non-function sort, and Boolean literals, require no recursive translation:

x:τF(x)=(x,∅,∅)c:τF(c)=(c^,∅,∅)v∈{true,false}F(v)=(v,∅,∅)\begin{aligned} x : \tau&\qquad\mathcal{F}(x) = (x, \varnothing, \varnothing) \\ c : \tau&\qquad\mathcal{F}(c) = (\hat{c}, \varnothing, \varnothing) \\ v \in\{\mathrm{true},\mathrm{false}\} &\qquad\mathcal{F}(v) = (v, \varnothing, \varnothing) \end{aligned}

Applications. The helper Ah(uˉ)=(t,Ch,Eh)A_h(\bar{u}) = (t, C^h, E^h) applies a head h:θh : \theta to a complete list of first-order arguments uˉ\bar{u}, returning a term and the head’s auxiliary axioms. Here cc is a constant, ff a bound variable, and ℓ\ell a lambda; uiu_i has sort σi\sigma_i.

c:θAc(uˉ)=(c^(uˉ),∅,∅)f:θAf(uˉ)=(app⁡θ(f,uˉ),∅,∅)(1)\frac{c : \theta}{A_c(\bar{u}) = (\hat{c}(\bar{u}), \varnothing, \varnothing)} \qquad \frac{f : \theta}{A_f(\bar{u}) = (\operatorname{app}_{\theta}(f,\bar{u}), \varnothing, \varnothing)} \tag*{(1)}
ℓ:θF(ℓ)=(ℓb,Cℓ,Eℓ)Aℓ(uˉ)=(app⁡θ(ℓb,uˉ),Cℓ,Eℓ)(2)\frac{\ell: \theta\qquad\mathcal{F}(\ell) = (\ell^b,C_\ell,E_\ell)} {A_\ell(\bar{u}) = (\operatorname{app}_{\theta}(\ell^b,\bar{u}),C_\ell,E_\ell)} \tag*{(2)}

The application rule translates every argument before applying the head:

h:θF(ai)=(aib,Cai,Eai) (1≤i≤n)Ah(aˉb)=(t,Ch,Eh)F(h a1⋯an)=(t,Ch∪⋃iCai,Eh∪⋃iEai)(3)\frac{h : \theta\qquad\mathcal{F}(a_i) = (a_i^b,C_{a_i},E_{a_i})\ (1 \le i \le n) \qquad A_h(\bar{a}^b) = (t,C^h,E^h)} {\mathcal{F}(h\ a_1 \cdots a_n) = \left(t,C^h \cup\bigcup_i C_{a_i},E^h \cup\bigcup_i E_{a_i}\right)} \tag*{(3)}

Equality and logical connectives. Equality at function sort additionally generates the extensionality axiom ext⁡θ\operatorname{ext}_{\theta}:

u,v:τF(u)=(ub,Cu,Eu)F(v)=(vb,Cv,Ev)F(u=v)=(ub=vb,Cu∪Cv,Eu∪Ev)\frac{u,v : \tau\qquad\mathcal{F}(u) = (u^b,C_u,E_u) \qquad\mathcal{F}(v) = (v^b,C_v,E_v)} {\mathcal{F}(u=v) = (u^b=v^b,C_u \cup C_v,E_u \cup E_v)}
u,v:θF(u)=(ub,Cu,Eu)F(v)=(vb,Cv,Ev)F(u=v)=(ub=vb,Cu∪Cv,Eu∪Ev∪{ext⁡θ})\frac{u,v : \theta\qquad\mathcal{F}(u) = (u^b,C_u,E_u) \qquad\mathcal{F}(v) = (v^b,C_v,E_v)} {\mathcal{F}(u=v) = (u^b=v^b,C_u \cup C_v,E_u \cup E_v \cup\{\operatorname{ext}_{\theta}\})}
ext⁡θ=(∀f,g:Fnθ.(∀xˉ.app⁡θ(f,xˉ)=app⁡θ(g,xˉ))→f=g).\operatorname{ext}_{\theta} = \left(\forall f,g : \mathrm{Fn}_{\theta}.\left(\forall\bar{x}.\operatorname{app}_{\theta}(f,\bar{x}) = \operatorname{app}_{\theta}(g,\bar{x})\right) \to f=g\right).

For logical connectives and quantifiers, let ∘∈{∧,∨,→,↔}\circ\in\{\land,\lor,\to,\leftrightarrow\} and Q∈{∀,∃}Q \in\{\forall,\exists\}:

F(p)=(pb,Cp,Ep)F(¬p)=(¬pb,Cp,Ep)F(p)=(pb,Cp,Ep)F(Qx:σ. p)=(Qx:σ. pb,Cp,Ep)F(p)=(pb,Cp,Ep)F(q)=(qb,Cq,Eq)F(p∘q)=(pb∘qb,Cp∪Cq,Ep∪Eq)\begin{aligned} \mathcal{F}(p) &= (p^b,C_p,E_p) & \mathcal{F}(\neg p) &= (\neg p^b,C_p,E_p) \\ \mathcal{F}(p) &= (p^b,C_p,E_p) & \mathcal{F}(Qx : \sigma.\ p) &= (Qx : \sigma.\ p^b,C_p,E_p) \\ \mathcal{F}(p) &= (p^b,C_p,E_p) & \mathcal{F}(q) &= (q^b,C_q,E_q) \\ \mathcal{F}(p \circ q) &= (p^b \circ q^b,C_p \cup C_q,E_p \cup E_q) \end{aligned}

Opening function bodies. To cover partial applications and lambdas whose bodies still have function type, define a helper B(e,zˉ)=(r,C,E)\mathcal{B}(e,\bar{z}) = (r,C,E) that translates ee applied to fresh parameters zˉ\bar{z} until its result is non-function. The parameter types are the complete argument list of the type of ee; zˉ\bar{z} is empty when ee has non-function type. Substitution below is capture-avoiding.

e:τF(e)=(r,C,E)B(e,())=(r,C,E)B(b[z0/x],zˉ)=(r,C,E)B(λx.b,(z0,zˉ))=(r,C,E)(4)\frac{e:\tau\qquad\mathcal{F}(e)=(r,C,E)}{\mathcal{B}(e,())=(r,C,E)} \qquad \frac{\mathcal{B}(b[z_0/x],\bar{z})=(r,C,E)}{\mathcal{B}(\lambda x.b,(z_0,\bar{z}))=(r,C,E)} \tag*{(4)}

For a non-lambda term h aˉh\ \bar{a}, the remaining parameters complete the application. The list aˉ=(a1,…,am)\bar{a}=(a_1,\ldots,a_m) may be empty for a variable or constant, and zˉ\bar{z} contains the remaining n−mn-m parameters.

h:θm<nF(ai)=(aib,Cai,Eai) (1≤i≤m)Ah(aˉ,zˉ)=(r,Ch,Eh)B(h aˉ,zˉ)=(r,Ch∪⋃iCai,Eh∪⋃iEai)(5)\frac{h:\theta\qquad m<n \qquad\mathcal{F}(a_i)=(a_i^b,C_{a_i},E_{a_i})\ (1\le i\le m) \qquad\mathcal{A}_h(\bar{a},\bar{z})=(r,C^h,E^h)}{\mathcal{B}(h\ \bar{a},\bar{z})=\left(r,C^h\cup\bigcup_i C_{a_i},E^h\cup\bigcup_i E_{a_i}\right)} \tag*{(5)}

Fresh parameters are passed as first-order variables, including when their types are function types.

Closure construction. For any function-valued e:θe:\theta, let ℓ\ell be its lambda form obtained by opening leading lambda binders and η\eta-expanding over any remaining arguments. Let yˉ\bar{y} be its free variables and zˉ\bar{z} fresh parameters for all arguments of θ\theta.

e:θℓ=λxˉ.e xˉyˉ=FV⁡(ℓ)B(e,zˉ)=(r,C,E)F(e)=(clos⁡ℓ(yˉ),C∪{Kℓ},E)(6)\begin{aligned} e:\theta\qquad&\ell=\lambda\bar{x}.e\ \bar{x} \qquad\bar{y}=\operatorname{FV}(\ell) \qquad\mathcal{B}(e,\bar{z})=(r,C,E)\\ \mathcal{F}(e)&=\left(\operatorname{clos}_{\ell}(\bar{y}),C\cup\{K_{\ell}\},E\right) \tag*{(6)} \end{aligned}
Kℓ=∀yˉ,zˉ.app⁡θ(clos⁡ℓ(yˉ),zˉ)=r.K_{\ell}=\forall\bar{y},\bar{z}.\operatorname{app}_{\theta}(\operatorname{clos}_{\ell}(\bar{y}),\bar{z})=r.

This generalizes the lambda clause of Figure 9 and defines the function-valued variable, constant, and partial-application cases. Captures are passed directly as bound variables, without η\eta-expansion. Opening nested lambda binders together avoids intermediate closures.

Model Extension

For any higher-order model MM, we construct its canonical first-order extension M⋆M^\star by retaining the carriers of base types and interpreting Fn⁡θ\operatorname{Fn}_{\theta} by the function space interpreting θ\theta. The interpretation of app⁡θ\operatorname{app}_{\theta} applies its function argument to the supplied arguments. The interpretation of cc is the uncurried form of M(c)M(c). A closure symbol reconstructs the captured environment and evaluates the corresponding lambda. This defines one interpretation for all generated symbols, independent of the particular formula being translated (see Definition 4).

Proof of Preservation of Denotations

Proof (of Lemma 1). We fix a higher-order model MM and its extension M⋆M^\star from Definition 4. We first establish 3 valuation identities by structural induction. For a type-preserving renaming π\pi, write e[π]e[\pi] for the renamed term and (ρ∘π)(x)=ρ(π(x))(\rho\circ\pi)(x)=\rho(\pi(x)). Then

⟦e[π]⟧M(ρ)=⟦e⟧M(ρ∘π).(7)\llbracket e[\pi]\rrbracket_M(\rho)=\llbracket e\rrbracket_M(\rho\circ\pi). \tag*{(7)}

Agreement on free variables gives the rule

∀x∈FV⁡(e). ρ1(x)=ρ2(x)⟦e⟧M(ρ1)=⟦e⟧M(ρ2)(8)\frac{\forall x \in\operatorname{FV}(e).\ \rho_1(x)=\rho_2(x)}{\llbracket e \rrbracket_M(\rho_1)=\llbracket e \rrbracket_M(\rho_2)} \tag*{(8)}

In the binder cases, the induction hypothesis applies after extending both valuations with the same value. These identities also hold for FO terms.

For fresh zz, the lambda and application semantics give

⟦λz.e z⟧M(ρ)=(fun⁡v⇒⟦e⟧M(ρ) v)=⟦e⟧M(ρ).\llbracket\lambda z.e\,z \rrbracket_M(\rho) = (\operatorname{fun} v \Rightarrow\llbracket e \rrbracket_M(\rho)\,v) = \llbracket e \rrbracket_M(\rho).

Repeated η\eta-expansion therefore preserves the denotation of the lambda form ℓ\ell used in Eq. (6).

We prove preservation for FF simultaneously with the following properties of the two helpers, by induction on the translation derivations. Each property quantifies over every valuation ρ\rho and wˉ\bar{w}:

Ah(uˉ)=(t,C,E)⟦t⟧M⋆(ρ)=⟦h⟧M(ρ)⟦u1⟧M⋆(ρ)⋯⟦un⟧M⋆(ρ)(9)\frac{A_h(\bar{u})=(t,C,E)}{\llbracket t \rrbracket_{M^\star}(\rho)=\llbracket h \rrbracket_M(\rho)\llbracket u_1 \rrbracket_{M^\star}(\rho)\cdots\llbracket u_n \rrbracket_{M^\star}(\rho)} \tag*{(9)}
B(e,zˉ)=(r,C,E)⟦r⟧M⋆(ρ[zˉ↦wˉ])=⟦e⟧M(ρ) w1⋯wn(10)\frac{B(e,\bar{z})=(r,C,E)}{\llbracket r \rrbracket_{M^\star}(\rho[\bar{z}\mapsto\bar{w}])=\llbracket e \rrbracket_M(\rho)\,w_1\cdots w_n} \tag*{(10)}

In Eq. (10), zˉ\bar{z} is fresh for ee and wˉ\bar{w} is any tuple of values of the corresponding sorts. For an empty tuple, application to wˉ\bar{w} leaves the value unchanged.

Base Case: Variables, Constants, and Literals. For x,c:τx,c:\tau where τ\tau is a non-function type, the base translation rules and Figure 8 yield

⟦xb⟧M⋆(ρ)=⟦x⟧M(ρ)=ρ(x)\llbracket x^b \rrbracket_{M^\star}(\rho)=\llbracket x \rrbracket_M(\rho)=\rho(x)
⟦cb⟧M⋆(ρ)=⟦c⟧M(ρ)=M(c)\llbracket c^b \rrbracket_{M^\star}(\rho)=\llbracket c \rrbracket_M(\rho)=M(c)

The Boolean-literal rule preserves True and False. For vi=⟦ui⟧M⋆(ρ)v_i=\llbracket u_i\rrbracket_{M^\star}(\rho), their interpretations give

⟦c^(uˉ)⟧M⋆(ρ)=M(c) v1⋯vn,\llbracket\widehat{c}(\bar{u}) \rrbracket_{M^\star}(\rho)=M(c)\,v_1\cdots v_n,
⟦app⁡θ(f,uˉ)⟧M⋆(ρ)=ρ(f) v1⋯vn.\llbracket\operatorname{app}_{\theta}(f,\bar{u}) \rrbracket_{M^\star}(\rho)=\rho(f)\,v_1\cdots v_n.

This completes the proof of Eq. (9) for constant and variable head (Eq. (1)).

Closure Case. The induction hypothesis is Eq. (10) for the recursive call B(e,zˉ)B(e,\bar{z}). Preservation of the closure term itself follows directly from its interpretation. In Eq. (6), let vˉ=ρ(yˉ)\bar{v}=\rho(\bar{y}). Since yˉ=FV⁡(ℓ)\bar{y}=\operatorname{FV}(\ell), the captured valuation ρℓ,vˉ\rho_{\ell,\bar{v}} agrees with ρ\rho on every free variable of ℓ\ell. Thus

⟦eb⟧M⋆(ρ)=M⋆(clos⁡ℓ)(vˉ)Eq. (6), Fig. 8=⟦ℓ⟧M(ρℓ,vˉ)Definition 4=⟦ℓ⟧M(ρ)Eq. (8)=⟦e⟧M(ρ)η-expansion.\begin{aligned} \llbracket e^b \rrbracket_{M^\star}(\rho) &=M^\star(\operatorname{clos}\ell)(\bar{v}) && \text{Eq. (6), Fig. 8}\\ &=\llbracket\ell\rrbracket_M(\rho_{\ell,\bar{v}}) && \text{Definition 4}\\ &=\llbracket\ell\rrbracket_M(\rho) && \text{Eq. (8)}\\ &=\llbracket e \rrbracket_M(\rho) && \eta\text{-expansion.} \end{aligned}

This covers lambdas and the η\eta-expanded forms of function-valued variables, constants, and partial applications.

Lambda Case. The induction hypothesis for the recursive call F(ℓ)F(\ell) is ⟦ℓb⟧M⋆(ρ)=⟦ℓ⟧M(ρ)\llbracket\ell^{b}\rrbracket_{M^{\star}}(\rho)=\llbracket\ell\rrbracket_{M}(\rho) for every ρ\rho. Let vi=⟦ui⟧M⋆(ρ)v_i=\llbracket u_i\rrbracket_{M^{\star}}(\rho). The rule in Eq. (2) and the interpretation of app⁡θ\operatorname{app}_{\theta} give

⟦app⁡θ(ℓb,uˉ)⟧M⋆(ρ)=⟦ℓb⟧M⋆(ρ) v1⋯vn=⟦ℓ⟧M(ρ) v1⋯vn.\begin{aligned} \llbracket\operatorname{app}_{\theta}(\ell^{b},\bar{u})\rrbracket_{M^{\star}}(\rho) &=\llbracket\ell^{b}\rrbracket_{M^{\star}}(\rho)\,v_1\cdots v_n\\ &=\llbracket\ell\rrbracket_{M}(\rho)\,v_1\cdots v_n. \end{aligned}

This establishes Eq. (9) for a lambda head.

Application Case. The induction hypotheses are ⟦aib⟧M⋆(ρ)=⟦ai⟧M(ρ)\llbracket a_i^{b}\rrbracket_{M^{\star}}(\rho)=\llbracket a_i\rrbracket_{M}(\rho) for every argument aia_i, and Eq. (9) for Ah(aˉ)A_h(\bar{a}), all at every valuation ρ\rho. Applying them to Eq. (3) gives

⟦(h aˉ)b⟧M⋆(ρ)=⟦h⟧M(ρ) ⟦a1b⟧M⋆(ρ)⋯⟦anb⟧M⋆(ρ)=⟦h⟧M(ρ) ⟦a1⟧M(ρ)⋯⟦an⟧M(ρ)=⟦h aˉ⟧M(ρ).\begin{aligned} \llbracket(h\,\bar{a})^{b}\rrbracket_{M^{\star}}(\rho) &=\llbracket h\rrbracket_{M}(\rho)\,\llbracket a_1^{b}\rrbracket_{M^{\star}}(\rho)\cdots\llbracket a_n^{b}\rrbracket_{M^{\star}}(\rho)\\ &=\llbracket h\rrbracket_{M}(\rho)\,\llbracket a_1\rrbracket_{M}(\rho)\cdots\llbracket a_n\rrbracket_{M}(\rho)\\ &=\llbracket h\,\bar{a}\rrbracket_{M}(\rho). \end{aligned}

Equality Case. The induction hypotheses, for every ρ\rho, are

⟦ub⟧M⋆(ρ)=⟦u⟧M(ρ),\llbracket u^{b}\rrbracket_{M^{\star}}(\rho)=\llbracket u\rrbracket_{M}(\rho),
⟦vb⟧M⋆(ρ)=⟦v⟧M(ρ).\llbracket v^{b}\rrbracket_{M^{\star}}(\rho)=\llbracket v\rrbracket_{M}(\rho).

The equality translation rule and Figure 8 give

⟦ub=vb⟧M⋆(ρ)=(⟦ub⟧M⋆(ρ)=⟦vb⟧M⋆(ρ))=(⟦u⟧M(ρ)=⟦v⟧M(ρ))=⟦u=v⟧M(ρ).\begin{aligned} \llbracket u^{b}=v^{b}\rrbracket_{M^{\star}}(\rho) &=\left(\llbracket u^{b}\rrbracket_{M^{\star}}(\rho)=\llbracket v^{b}\rrbracket_{M^{\star}}(\rho)\right)\\ &=\left(\llbracket u\rrbracket_{M}(\rho)=\llbracket v\rrbracket_{M}(\rho)\right)\\ &=\llbracket u=v\rrbracket_{M}(\rho). \end{aligned}

This applies to equality at both function and non-function sorts.

Negation Case. The induction hypothesis is ⟦pb⟧M⋆(ρ)=⟦p⟧M(ρ)\llbracket p^{b}\rrbracket_{M^{\star}}(\rho)=\llbracket p\rrbracket_{M}(\rho) for every ρ\rho. By the negation translation rule and its semantics,

⟦¬pb⟧M⋆(ρ)=¬⟦pb⟧M⋆(ρ)=¬⟦p⟧M(ρ)=⟦¬p⟧M(ρ).\begin{aligned} \llbracket\neg p^{b}\rrbracket_{M^{\star}}(\rho) &=\neg\llbracket p^{b}\rrbracket_{M^{\star}}(\rho)\\ &=\neg\llbracket p\rrbracket_{M}(\rho)\\ &=\llbracket\neg p\rrbracket_{M}(\rho). \end{aligned}

Binary Connective Case. The induction hypotheses are preservation for pp and qq at every ρ\rho. For ∘∈{∧,∨,→,↔}\mathbin{\circ}\in\{\land,\lor,\to,\leftrightarrow\},

⟦pb∘qb⟧M⋆(ρ)=⟦pb⟧M⋆(ρ)∘⟦qb⟧M⋆(ρ)=⟦p⟧M(ρ)∘⟦q⟧M(ρ)=⟦p∘q⟧M(ρ).\begin{aligned} \llbracket p^{b}\mathbin{\circ}q^{b}\rrbracket_{M^{\star}}(\rho) &=\llbracket p^{b}\rrbracket_{M^{\star}}(\rho)\mathbin{\circ}\llbracket q^{b}\rrbracket_{M^{\star}}(\rho)\\ &=\llbracket p\rrbracket_{M}(\rho)\mathbin{\circ}\llbracket q\rrbracket_{M}(\rho)\\ &=\llbracket p\mathbin{\circ}q\rrbracket_{M}(\rho). \end{aligned}

Quantifier Case. The induction hypothesis is preservation for pp at every extended valuation:

∀ρ,v.⟦pb⟧M⋆(ρ[x↦v])=⟦p⟧M(ρ[x↦v]).\forall\rho,v.\quad\llbracket p^{b}\rrbracket_{M^{\star}}(\rho[x\mapsto v])=\llbracket p\rrbracket_{M}(\rho[x\mapsto v]).

For Q∈{∀,∃}Q \in\{\forall, \exists\}, corresponding sorts have the same carriers (i.e., ⟦σ♭⟧M⋆=⟦σ⟧M\llbracket\sigma^\flat\rrbracket_{M^\star} = \llbracket\sigma\rrbracket_M), so the quantifier translation rule gives

⟦Qx:σ♭.p♭⟧M⋆(ρ)=Qv:⟦σ♭⟧M⋆.⟦p♭⟧M⋆(ρ[x↦v])=Qv:⟦σ⟧M.⟦p⟧M(ρ[x↦v])=⟦Qx:σ.p⟧M(ρ).\llbracket Qx : \sigma^\flat. p^\flat\rrbracket_{M^\star}(\rho) = Qv : \llbracket\sigma^\flat\rrbracket_{M^\star}. \llbracket p^\flat\rrbracket_{M^\star}(\rho[x \mapsto v]) = Qv : \llbracket\sigma\rrbracket_M. \llbracket p \rrbracket_M(\rho[x \mapsto v]) = \llbracket Qx : \sigma. p \rrbracket_M(\rho).

Non-function Body Case. The induction hypothesis for F(e)=(r,C,E)\mathcal{F}(e) = (r, C, E) is

∀ρ. ⟦r⟧M⋆(ρ)=⟦e⟧M(ρ).\forall\rho.\ \llbracket r \rrbracket_{M^\star}(\rho) = \llbracket e \rrbracket_M(\rho).

The non-function rule in Eq. (4) has no fresh parameters, so this is exactly Eq. (10).

Lambda Body Case. The induction hypothesis for B(b[z0/x],zˉ)=(r,C,E)\mathcal{B}(b[z_0/x], \bar{z}) = (r, C, E) is

∀ρ′,wˉ. ⟦r⟧M⋆(ρ′[zˉ↦wˉ])=⟦b[z0/x]⟧M(ρ′)wˉ.\forall\rho', \bar{w}.\ \llbracket r \rrbracket_{M^\star}(\rho'[\bar{z} \mapsto\bar{w}]) = \llbracket b[z_0/x] \rrbracket_M(\rho')\bar{w}.

Here, application to a tuple abbreviates successive application. To prove Eq. (10) for B(λx.b,(z0,zˉ))=(r,C,E)\mathcal{B}(\lambda x.b, (z_0, \bar{z})) = (r, C, E), we need to prove

∀ρ,w0,wˉ. ⟦r⟧M⋆(ρ[z0↦w0,zˉ↦wˉ])=⟦λx.b⟧M(ρ) w0 wˉ.\forall\rho, w_0, \bar{w}.\ \llbracket r \rrbracket_{M^\star}(\rho[z_0 \mapsto w_0, \bar{z} \mapsto\bar{w}]) = \llbracket\lambda x.b \rrbracket_M(\rho)\,w_0\,\bar{w}.

Let ρ′=ρ[z0↦w0]\rho' = \rho[z_0 \mapsto w_0]. The lambda rule in Eq. (4), Eq. (7) give

⟦r⟧M⋆(ρ[z0↦w0,zˉ↦wˉ])=⟦r⟧M⋆(ρ′[zˉ↦wˉ])=⟦b[z0/x]⟧M(ρ′)wˉ=⟦b[z0/x]⟧M(ρ[z0↦w0])wˉ=⟦b⟧M(ρ[x↦w0])wˉ=⟦λx.b⟧M(ρ) w0 wˉ.\begin{aligned} \llbracket r \rrbracket_{M^\star}(\rho[z_0 \mapsto w_0, \bar{z} \mapsto\bar{w}]) &= \llbracket r \rrbracket_{M^\star}(\rho'[\bar{z} \mapsto\bar{w}]) \\ &= \llbracket b[z_0/x] \rrbracket_M(\rho')\bar{w} \\ &= \llbracket b[z_0/x] \rrbracket_M(\rho[z_0 \mapsto w_0])\bar{w} \\ &= \llbracket b \rrbracket_M(\rho[x \mapsto w_0])\bar{w} \\ &= \llbracket\lambda x.b \rrbracket_M(\rho)\,w_0\,\bar{w}. \end{aligned}

Partial Application Body Case. The induction hypotheses are preservation for each supplied argument aia_i and Eq. (9) for Ah(aˉ,zˉ)A_h(\bar{a}, \bar{z}), at every valuation. For Eq. (5), let ρ′=ρ[zˉ↦wˉ]\rho' = \rho[\bar{z} \mapsto\bar{w}]. These hypotheses and freshness of zˉ\bar{z} give

⟦r⟧M⋆(ρ′)=⟦h⟧M(ρ′)⟦a1⟧M⋆(ρ′)⋯⟦am⟧M⋆(ρ′)wˉ=⟦haˉ⟧M(ρ)wˉ.\begin{aligned} \llbracket r \rrbracket_{M^\star}(\rho') &= \llbracket h \rrbracket_M(\rho')\llbracket a_1 \rrbracket_{M^\star}(\rho')\cdots\llbracket a_m \rrbracket_{M^\star}(\rho')\bar{w} \\ &= \llbracket h\bar{a} \rrbracket_M(\rho)\bar{w}. \end{aligned}

This establishes Eq. (10) and completes the recursive cases.

Proof of Validity of Generated Axioms

Proof (of Lemma 2). We fix MM and proceed by induction on the translation derivations: M⋆⊨C∪EM^\star\models C \cup E whenever F\mathcal{F}, A\mathcal{A}, or B\mathcal{B} returns auxiliary sets C,EC, E. We use the following consequence of Definition 1 to combine these sets:

M⋆⊨S1⋯M⋆⊨SkM⋆⊨⋃i=1kSi(11)\frac{M^\star\models S_1 \quad\cdots\quad M^\star\models S_k}{M^\star\models\bigcup_{i=1}^{k} S_i} \tag*{(11)}

Base Case: Variables, Constants, and Literals. The base rules for FF, and the constant and variable head rules for AA, generate C=E=∅C = E = \varnothing (i.e., ⊤\top). Thus M⋆⊨C∪EM^\star\models C \cup E holds vacuously.

Closure Case. The induction hypothesis for B(e,zˉ)=(r,C,E)B(e,\bar{z}) = (r,C,E) is M⋆⊨C∪EM^\star\models C \cup E. It remains to establish the newly generated closure equation KℓK_\ell. For Eq. (6), take any valuation ρ\rho and let vˉ=ρ(yˉ)\bar{v} = \rho(\bar{y}) and wˉ=ρ(zˉ)\bar{w} = \rho(\bar{z}). Then

⟦app⁡θ(clos⁡ℓ(yˉ),zˉ)⟧M⋆(ρ)=⟦ℓ⟧M(ρℓ,vˉ)wˉ=⟦e⟧M(ρ)wˉ=⟦r⟧M⋆(ρ).\begin{aligned} \llbracket\operatorname{app}_{\theta}(\operatorname{clos}_{\ell}(\bar{y}),\bar{z}) \rrbracket_{M^\star}(\rho) &= \llbracket\ell\rrbracket_M(\rho\ell,\bar{v})\bar{w}\\ &= \llbracket e \rrbracket_M(\rho)\bar{w}\\ &= \llbracket r \rrbracket_{M^\star}(\rho). \end{aligned}

The first equality unfolds Definition 4; the second uses Eq. (8) and $\eta$-expansion; the third uses Eq. (10). By equality and universal quantification in Figure 8,

∀ρ. ⟦app⁡θ(clos⁡ℓ(yˉ),zˉ)⟧M⋆(ρ)=⟦r⟧M⋆(ρ)M⋆⊨{Kℓ}\frac{\forall\rho.\ \llbracket\operatorname{app}_{\theta}(\operatorname{clos}_{\ell}(\bar{y}),\bar{z}) \rrbracket_{M^\star}(\rho) = \llbracket r \rrbracket_{M^\star}(\rho)}{M^\star\models\{K_\ell\}}

Combining this with the induction hypothesis gives M⋆⊨C∪{Kℓ}∪EM^\star\models C \cup\{K_\ell\} \cup E, as required by the closure rule.

Function Equality Case. The induction hypotheses are M⋆⊨Cu∪EuM^\star\models C_u \cup E_u and M⋆⊨Cv∪EvM^\star\models C_v \cup E_v. It remains to establish the newly generated axiom ext⁡θ\operatorname{ext}_{\theta}. Let F,G∈⟦Fnθ⟧M⋆F,G \in\llbracket\mathrm{Fn}_{\theta} \rrbracket_{M^\star} satisfy the premise of ext⁡θ\operatorname{ext}_{\theta}. Definition 4 interprets these values as functions in ⟦θ⟧M\llbracket\theta\rrbracket_M and app⁡θ\operatorname{app}_{\theta} as their application. Then,

∀w1,…,wn. Fw1⋯wn=Gw1⋯wnF=G(function extensionality).\frac{\forall w_1,\ldots,w_n.\ Fw_1\cdots w_n = Gw_1\cdots w_n}{F = G} \qquad\text{(function extensionality).}

Since FF and GG are arbitrary, the implication and quantifier semantics give M⋆⊨{ext⁡θ}M^\star\models\{\operatorname{ext}_{\theta}\}. Together with the induction hypotheses, this yields

M⋆⊨Cu∪Cv∪Eu∪Ev∪{ext⁡θ}.M^\star\models C_u \cup C_v \cup E_u \cup E_v \cup\{\operatorname{ext}_{\theta}\}.

Application and Partial Application Body Cases. The induction hypotheses are M⋆⊨Ch∪EhM^\star\models C^h \cup E^h for the head and M⋆⊨Cai∪EaiM^\star\models C_{a_i} \cup E_{a_i} for every supplied argument. Taking their union gives

M⋆⊨(Ch∪⋃iCai)∪(Eh∪⋃iEai),M^\star\models(C^h \cup\bigcup_i C_{a_i}) \cup(E^h \cup\bigcup_i E_{a_i}),

which is the output of Eqs. (3) and (5).

Non-function Equality and Binary Connective Cases. The induction hypotheses give validity of the auxiliary sets for each operand. These rules return their union, whose validity follows from the union rule above.

Negation and Quantifier Cases. The induction hypothesis is M⋆⊨Cp∪EpM^\star\models C_p \cup E_p for the body pp. Both rules retain these same sets. The generated axioms are already closed, so their validity is independent of the quantifier’s bound value.

Lambda and Non-function Body Cases. The induction hypothesis is validity of the sets returned by F(ℓ)F(\ell) or F(e)F(e), respectively. The corresponding rules for AA and BB return those sets unchanged.

Lambda Body Case. The induction hypothesis gives M⋆⊨C∪EM^\star\models C \cup E for the sets returned by B(b[z/x],zˉ)B(b[z/x],\bar{z}). The lambda rule in Eq. (4) retains these sets; renaming preserves validity by Eq. (7). This completes all cases. □\square

Proof of Soundness

Proof (of Theorem 1). We suppose D(T)D(T) is unsatisfiable and, for contradiction, assume a higher-order model MM satisfying TT. We construct M⋆M^\star as in Definition 4. By satisfaction and Lemma 1, for each φ∈T\varphi\in T we have:

M⊨Tφ∈T⟦φb⟧M⋆(∅)=⟦φ⟧M(∅)M⋆⊨{φb}\frac{M \models T \qquad\varphi\in T \qquad\llbracket\varphi^{b} \rrbracket_{M^\star}(\varnothing)=\llbracket\varphi\rrbracket_M(\varnothing)}{M^\star\models\{\varphi^{b}\}}

Lemma 2 supplies the auxiliary formulas. The same M⋆M^\star interprets the symbols of every translated formula, so Definition 3 gives

∀φ∈T. M⋆⊨{φb}∀φ∈T. M⋆⊨Cφ∪EφM⋆⊨D(T)\frac{\forall\varphi\in T.\ M^\star\models\{\varphi^{b}\} \qquad\forall\varphi\in T.\ M^\star\models C_\varphi\cup E_\varphi}{M^\star\models D(T)}

This contradicts the assumed unsatisfiability:

M⋆⊨D(T)¬∃N. N⊨D(T)⊥\frac{M^\star\models D(T) \qquad\neg\exists N.\ N \models D(T)}{\bot}

Hence no MM satisfies TT, and TT is unsatisfiable. □\square

Scope of Formalization

The language is monomorphic and nondependent. It contains no datatype constructors, pattern matching, or built-in arithmetic and bitvector operations. Such types and operations can be treated abstractly as base types and constants, but their concrete SMT encodings are not justified by this proof. Each base type has its own carrier, so the formalization also excludes embeddings into a larger sort and the guarded closure, application-result, and extensionality axioms used for those embeddings. Solver-native higher-order translation is not modeled.

There are two gaps remaining in the formalization. First, no mechanized result connects a Lean expression to a formula of this higher-order language. Second, first-order models interpret the entire collection of structurally identified symbols, whereas an SMT script declares a finite set of named symbols. Connecting these representations requires showing that all symbols occurring in the generated formulas are declared and that distinct structural symbols receive distinct names. We aim to complete these formalizations in future work.

Reconstruction Procedures

Figure 13 sketches reconstruction of a Lean goal GG. F(i):AiF(i) : A_i is the retained Lean proof for assertion ii, UU is the UNSAT core, and Π\Pi is the solver proof. R\mathcal{R} contains registered reconstruction lemmas, T\mathcal{T} contains finishing tactics, and bb bounds backward search. A substitution σ\sigma instantiates lemma parameters or binds handler captures. In the proof search procedure, crush first tries the supplied finisher tactics (such as omega), given the premises in the UNSAT core. If none of them can close the goal, crush then tries to match the current goal against the registered reconstruction lemma. If a lemma’s conclusion matches the goal, it tries to apply the lemma and recursively search the proof for the premises of the lemma.

Core-guided reconstruction and proof replay procedures

Figure 13. Core-guided reconstruction (left) and proof replay (right).

In replay of solver inference steps, δ\delta decodes SMT clauses using term handlers; Hr\mathcal{H}_r includes handlers for rule rr. A step records its identifier (ii), rule (rr), clause (CC), premise identifiers (jˉ\bar{j}), and arguments (aˉ\bar{a}). iGi_G is the negated goal. We use P[□]P[\Box] to denote the proof of the final empty clause. For each such step, crush uses δ(C)\delta(C) to obtain the corresponding Lean obligation AA. Then, it tries to match the pattern against the arguments. For a matching handler η\eta, crush uses η\eta to construct a proof term pp and, together with the previously constructed proof terms pˉ\bar{p}, checks if the reconstructed proof term has type AA. If any handler successfully closed the Lean obligation, crush records the constructed proof term and moves to the next step. If all handlers failed, crush will report the failure.

Trusted SMT Comparison

Table 5 reports the head-to-head comparison when crush trusts SMT results. It uses the same VCs and baselines as Table 2. Runtime means and standard deviations are computed separately for each pair over the VCs both tools discharge.

References

  1. [1]Appel, A.W.: Verified software toolchain: (invited talk). In: European Symposium on Programming. pp. 1–17. Springer (2011)
  2. [2]Armand, M., Faure, G., Grégoire, B., Keller, C., Théry, L., Werner, B.: A modular integration of sat/smt solvers to coq through proof witnesses. In: Proceedings of the First International Conference on Certified Programs and Proofs. p. 135–150. CPP’11, Springer-Verlag, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25379-9_12, https://doi.org/10.1007/978-3-642-25379-9_12
  3. [3]Barbosa, H., Barrett, C.W., Brain, M., Kremer, G., Lachnitt, H., Mann, M., Mohamed, A., Mohamed, M., Niemetz, A., Nötzli, A., Ozdemir, A., Preiner, M., Reynolds, A., Sheng, Y., Tinelli, C., Zohar, Y.: cvc5: A versatile and industrial-strength SMT solver. In: Fisman, D., Rosu, G. (eds.) Tools and Algorithms for the Construction and Analysis of Systems - 28th International Conference, TACAS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2-7, 2022, Proceedings, Part I. Lecture Notes in Computer Science, vol. 13243, pp. 415–442. Springer (2022). https://doi.org/10.1007/978-3-030-99524-9_24, https://doi.org/10.1007/978-3-030-99524-9_24
  4. [4]Barrett, C., Fontaine, P., Tinelli, C.: The SMT-LIB Standard: Version 2.7. Tech. rep., Department of Computer Science, The University of Iowa (2025), available at www.SMT-LIB.org
  5. [5]Blot, V., Cousineau, D., Crance, E., de Prisque, L.D., Keller, C., Mahboubi, A., Vial, P.: Compositional pre-processing for automated reasoning in dependent type theory. In: Proceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs. p. 63–77. CPP ’23, ACM (Jan 2023). https://doi.org/10.1145/3573105.3575676, http://dx.doi.org/10.1145/3573105.3575676
  6. [6]Böhme, S., Weber, T.: Fast lcf-style proof reconstruction for z3. In: International Conference on Interactive Theorem Proving. pp. 179–194. Springer (2010)DOI
  7. [7]Brooker, M., Desai, A.: Systems correctness practices at amazon web services. Commun. ACM 68(6), 38–42 (Jun 2025). https://doi.org/10.1145/3729175, https://doi.org/10.1145/3729175
  8. [8]Choi, J., Vijayaraghavan, M., Sherman, B., Chlipala, A., Arvind: Kami: a platform for high-level parametric hardware specification and its modular verification. Proceedings of the ACM on Programming Languages 1(ICFP), 1–30 (2017)DOI
  9. [9]Clune, J., Qian, Y., Bentkamp, A., Avigad, J.: Duper: A proof-producing superposition theorem prover for dependent type theory. In: International Conference on Interactive Theorem Proving (2024), https://api.semanticscholar.org/CorpusID:272330518DOI
  10. [10]Czajka, Ł., Kaliszyk, C.: Hammer for coq: Automation for dependent type theory. J. Autom. Reason. 61(1–4), 423–453 (Jun 2018). https://doi.org/10.1007/s10817-018-9458-4, https://doi.org/10.1007/s10817-018-9458-4 Mike He, Dexin Zhang, and Aarti Gupta
  11. [11]De Moura, L., Bjørner, N.: Z3: An efficient smt solver. In: International conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 337–340. Springer (2008)DOI
  12. [12]Desai, A., Gupta, V., Jackson, E., Qadeer, S., Rajamani, S., Zufferey, D.: P: safe asynchronous event-driven programming. SIGPLAN Not. 48(6), 321–332 (Jun 2013). https://doi.org/10.1145/2499370.2462184, https://doi.org/10.1145/2499370.2462184
  13. [13]Gladshtein, V., Kurin, V., Feng, Y., Kafle, D., Pirlea, G., Zhao, Q., Sergey, I.: Velvet: A foundational multi-modal verifier for imperative programs in lean. In: Computer Aided Verification: 38th International Conference, CAV 2026, Lisbon, Portugal, July 26–29, 2026, Proceedings, Part II. p. 228–242. Springer-Verlag, Berlin, Heidelberg (2026). https://doi.org/10.1007/978-3-032-32526-6_11, https://doi.org/10.1007/978-3-032-32526-6_11
  14. [14]Gladshtein, V., Pîrlea, G., Zhao, Q., Kurin, V., Sergey, I.: Foundational multi-modal program verifiers. Proc. ACM Program. Lang. 10(POPL) (Jan 2026). https://doi.org/10.1145/3776719, https://doi.org/10.1145/3776719
  15. [15]Hawblitzel, C., Howell, J., Kapritsos, M., Lorch, J.R., Parno, B., Roberts, M.L., Setty, S., Zill, B.: Ironfleet: proving practical distributed systems correct. In: Proceedings of the 25th Symposium on Operating Systems Principles. p. 1–17. SOSP ’15, Association for Computing Machinery, New York, NY, USA (2015). https://doi.org/10.1145/2815400.2815428, https://doi.org/10.1145/2815400.2815428
  16. [16]Kaivola, R., Ghughal, R., Narasimhan, N., Telfer, A., Whittemore, J., Pandav, S., Slobodová, A., Taylor, C., Frolov, V., Reeber, E., et al.: Replacing testing with formal verification in intel corem i7 processor execution engine validation. In: International Conference on Computer Aided Verification. pp. 414–429. Springer (2009)DOI
  17. [17]Klein, G., Elphinstone, K., Heiser, G., Andronick, J., Cock, D., Derrin, P., Elkaduwe, D., Engelhardt, K., Kolanski, R., Norris, M., Sewell, T., Tuch, H., Winwood, S.: seL4: formal verification of an os kernel. In: Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles. p. 207–220. SOSP ’09, Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145/1629575.1629596, https://doi.org/10.1145/1629575.1629596
  18. [18]Lab, V.: Loom — github.com. https://github.com/verse-lab/loom/tree/master/CaseStudies/Cashmere, [Accessed 09-10-2026]
  19. [19]Leroy, X., Blazy, S., Kästner, D., Schommer, B., Pister, M., Ferdinand, C.: Compcert-a formally verified optimizing compiler. In: ERTS 2016: Embedded Real Time Software and Systems, 8th European Congress (2016)
  20. [20]Limperg, J., From, A.H.: Aesop: White-box best-first proof search for lean. In: Proceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs. p. 253–266. CPP 2023, Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3573105.3575671, https://doi.org/10.1145/3573105.3575671
  21. [21]Mohamed, A., Mascarenhas, T., Khan, H., Barbosa, H., Reynolds, A., Qian, Y., Tinelli, C., Barrett, C.: lean-smt: An smt tactic for discharging proof goals in lean. In: Computer Aided Verification: 37th International Conference, CAV 2025, Zagreb, Croatia, July 23–25, 2025, Proceedings, Part III. p. 197–212. Springer-Verlag, Berlin, Heidel- berg (2025). https://doi.org/10.1007/978-3-031-98682-6_11, https://doi.org/10.1007/978-3-031-98682-6_11
  22. [22]Morrison, K., de Moura, L.: grind: An smt-inspired tactic for lean 4 (short paper – system description). In: Biere, A., Lutz, C., Negri, S. (eds.) Automated Reasoning. pp. 106–114. Springer Nature Switzerland, Cham (2026)DOI
  23. [23]de Moura, L., Ullrich, S.: The lean 4 theorem prover and programming language. In: Automated Deduction – CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12–15, 2021, Proceedings. p. 625–635. Springer-Verlag, Berlin, Heidelberg (2021). https://doi.org/10.1007/978-3-030-79876-5_37, https://doi.org/10.1007/978-3-030-79876-5_37
  24. [24]Nipkow, T., Wenzel, M., Paulson, L.C.: Isabelle/HOL: a proof assistant for higher-order logic. Springer-Verlag, Berlin, Heidelberg (2002)DOI
  25. [25]Norell, U.: Dependently typed programming in agda. In: Proceedings of the 4th International Workshop on Types in Language Design and Implementation. p. 1–2. TLDI ’09, Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145/1481861.1481862, https://doi.org/10.1145/1481861.1481862
  26. [26]P-Developers: Plean — github.com. https://github.com/p-org/P/tree/dev/p-lean/Src/PLean, [Accessed 09-10-2026]
  27. [27]Paulson, L.C., Susanto, K.W.: Source-level proof reconstruction for interactive theorem proving. In: Schneider, K., Brandt, J. (eds.) Theorem Proving in Higher Order Logics. pp. 232–245. Springer Berlin Heidelberg, Berlin, Heidelberg (2007)DOI
  28. [28]Qian, Y., Clune, J., Barrett, C., Avigad, J.: Lean-auto: An interface between lean 4 and automated theorem provers. In: Computer Aided Verification: 37th International Conference, CAV 2025, Zagreb, Croatia, July 23–25, 2025, Proceedings, Part III. p. 175–196. Springer-Verlag, Berlin, Heidelberg (2025). https://doi.org/10.1007/978-3-031-98682-6_10, https://doi.org/10.1007/978-3-031-98682-6_10
  29. [29]Reynolds, A., Schurr, H.J., Barbosa, H., Israel, O., Jakpor, J.Z., Lachnitt, H., Mohamed, A., Niemetz, A., Preiner, M., Zohar, Y., Jones, R., Barrett, C., Tinelli, C.: The cooperating proof calculus: Comprehensive proofs for an smt solver. In: Darulova, E., Lin, A.W., Rümmer, P. (eds.) Computer Aided Verification. pp. 188–212. Springer Nature Switzerland, Cham (2026)DOI
  30. [30]Russinoff, D.M.: A mechanically checked proof of ieee compliance of the floating point multiplication, division and square root algorithms of the amd-k7™ processor. LMS Journal of Computation and Mathematics 1, 148–200 (1998)
  31. [31]Schulz, S., Cruanes, S., Vukmirović, P.: Faster, higher, stronger: E 2.3. In: Automated Deduction – CADE 27: 27th International Conference on Automated Deduction, Natal, Brazil, August 27–30, 2019, Proceedings. p. 495–507. Springer-Verlag, Berlin, Heidelberg (2019). https://doi.org/10.1007/978-3-030-29436-6_29, https://doi.org/10.1007/978-3-030-29436-6_29
  32. [32]Schurr, H.J., Fleury, M., Barbosa, H., Fontaine, P.: Alethe: Towards a generic smt proof format. arXiv preprint arXiv:2107.02354 (2021)DOI
  33. [33]Sharma, U., Jung, R., Tassarotti, J., Kaashoek, F., Zeldovich, N.: Grove: a separation-logic library for verifying distributed systems. In: Proceedings of the 29th Symposium on Operating Systems Principles. p. 113–129. SOSP ’23, ACM (Oct 2023). https://doi.org/10.1145/3600006.3613172, https://doi.org/10.1145/3600006.3613172
  34. [34]Team, T.C.D.: The coq proof assistant (Sep 2024). https://doi.org/10.5281/zenodo.14542673, https://doi.org/10.5281/zenodo.14542673
  35. [35]Vukmirović, P., Bentkamp, A., Blanchette, J., Cruanes, S., Nummelin, V., Tourret, S.: Making Higher-Order Superposition Work. Journal of Automated Reasoning 66(4), 541–564 (Nov 2022). https://doi.org/10.1007/s10817-021-09613-z, https://inria.hal.science/hal-03909997
  36. [36]Zhu, T., Clune, J., Avigad, J., Jiang, A.Q., Welleck, S.: Premise selection for a lean hammer (2026), https://arxiv.org/abs/2506.07477

Paper details

vlnc:W_2yw7gepj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents