DecisionTree.buildFull_depth
theoremverifiedimported Lean
The complete tree started at level k has depth at most n - k.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma DecisionTree.buildFull_depth {n : ℕ} (f : (Fin n → Bool) → Bool) (k : ℕ) (_ : k ≤ n) (acc : Fin n → Bool) : (DecisionTree.buildFull f k acc).depth ≤ n - k
- Source
- TCSlib, `DecisionTree.buildFull_depth`
- 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_depth← DecisionTree.buildFull_depth (TCSlib/BooleanAnalysis/DecisionTree.lean:117): verbatim
- Verified
- 07 Oct 2026
- Axioms
Quot.soundpropext- Built on 2
- DecisionTree.buildFullBuild a complete decision tree querying variables 0, 1, …, n−1 in order.
- DecisionTree.depthThe depth of a decision tree (maximum path length to a leaf): a leaf has depth $0$ and a branch has depth $1$ plus the maximum of its two…
- 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 started at level `k` has depth at most `n - k`. -/lemma DecisionTree.buildFull_depth {n : ℕ} (f : (Fin n → Bool) → Bool) (k : ℕ) (_ : k ≤ n) (acc : Fin n → Bool) : (DecisionTree.buildFull f k acc).depth ≤ n - k := by unfold DecisionTree.buildFull split · rename_i h simp only [DecisionTree.depth] have h1 := DecisionTree.buildFull_depth f (k + 1) (by omega) (Function.update acc ⟨k, h⟩ false) have h2 := DecisionTree.buildFull_depth f (k + 1) (by omega) (Function.update acc ⟨k, h⟩ true) have h3 := max_le h1 h2 omega · simp [DecisionTree.depth]termination_by n - k