AFTD Auto-Formalizing Theoretical Domains

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.
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

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
See it in the graphDiscuss this resultChallenge it