DecisionTree.buildFull_eval
The complete tree computes f on every input it is consistent with. Proof sketch. Induction on the number of variables still to be queried, following the recursion that builds the tree. The invariant carried along is that the accumulator already agrees with the input on the coordinates queried so far. If variables remain, the tree branches on the next coordinate and evaluation follows the branch named by the input's value there; updating the accumulator at that coordinate to that same value extends the agreement by one coordinate, which is exactly the hypothesis the induction step needs. If none remain, the tree is the leaf holding f of the accumulator, and the invariant now covers every coordinate, so the accumulator and the input are equal as functions and the leaf is f of the input.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma DecisionTree.buildFull_eval {n : ℕ} (f : (Fin n → Bool) → Bool) (k : ℕ) (hk : k ≤ n) (acc x : Fin n → Bool) (hinv : ∀ i : Fin n, i.val < k → acc i = x i) : (DecisionTree.buildFull f k acc).eval x = f x
- Source
- TCSlib, `DecisionTree.buildFull_eval`
- Lean proof
- By Hydroxyi, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 TCSlib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.DecisionTree.buildFull_eval← DecisionTree.buildFull_eval (TCSlib/BooleanAnalysis/DecisionTree.lean:145): verbatim
- Verified
- 07 Oct 2026
- Axioms
Quot.soundpropext- Built on 3
- DecisionTree.buildFullBuild a complete decision tree querying variables 0, 1, …, n−1 in order.
- DecisionTreeA decision tree on $n$ Boolean variables: a leaf $\mathtt{leaf}\,b$ outputs $b$, and a branch $\mathtt{branch}\,i\,lo\,hi$ queries…
- DecisionTree.evalEvaluates a decision tree on an input $x$: a leaf returns its stored bit, and a branch on variable $i$ follows the high subtree when $x_i$…
- Used by 1
- dtDepthThe decision-tree depth of $f : (\mathrm{Fin}\,n \to \mathrm{Bool}) \to \mathrm{Bool}$ is the least $d$ such that some decision tree of…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- The complete tree computes `f` on every input it is consistent with. **Proof sketch.** Induction on the number of variables still to be queried, following the recursion that builds the tree. The invariant carried along is that the accumulator already agrees with the input on the coordinates queried so far. If variables remain, the tree branches on the next coordinate and evaluation follows the branch named by the input's value there; updating the accumulator at that coordinate to that same value extends the agreement by one coordinate, which is exactly the hypothesis the induction step needs. If none remain, the tree is the leaf holding `f` of the accumulator, and the invariant now covers every coordinate, so the accumulator and the input are equal as functions and the leaf is `f` of the input. -/lemma DecisionTree.buildFull_eval {n : ℕ} (f : (Fin n → Bool) → Bool) (k : ℕ) (hk : k ≤ n) (acc x : Fin n → Bool) (hinv : ∀ i : Fin n, i.val < k → acc i = x i) : (DecisionTree.buildFull f k acc).eval x = f x := by unfold DecisionTree.buildFull split · rename_i h simp only [DecisionTree.eval] cases hxv : x ⟨k, h⟩ with | false => rw [if_neg (by decide : ¬(false = true))] apply DecisionTree.buildFull_eval f (k + 1) (by omega) intro i hi by_cases heq : i = ⟨k, h⟩ · subst heq; simp [Function.update, hxv] · simp only [Function.update, heq] exact hinv i (by have : i.val ≠ k := fun hv => heq (Fin.ext hv); omega) | true => rw [if_pos rfl] apply DecisionTree.buildFull_eval f (k + 1) (by omega) intro i hi by_cases heq : i = ⟨k, h⟩ · subst heq; simp [Function.update, hxv] · simp only [Function.update, heq] exact hinv i (by have : i.val ≠ k := fun hv => heq (Fin.ext hv); omega) · simp only [DecisionTree.eval] have : acc = x := funext fun i => hinv i (by omega) rw [this]termination_by n - k