AFTD Auto-Formalizing Theoretical Domains

comparison_tree_depth_bind_le

theoremverified

If every continuation tree f a has depth at most d, then comparison_tree_bind T f has depth at most comparison_tree_depth T + d: comparison counts of staged algorithms add up.

Statement

theorem comparison_tree_depth_bind_le {n : ℕ} (T : ComparisonTree n) (f : Fin n → ComparisonTree n)
    (d : ℕ) (h : ∀ a, comparison_tree_depth (f a) ≤ d) :
    comparison_tree_depth (comparison_tree_bind T f) ≤ comparison_tree_depth T + d
Source
step towards v_selection_16_8_upper_bound
Verified
19 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • comparison_tree_bindComposition of comparison decision trees: run T, and at each leaf a continue with the tree f a. Recursion peels off the first stage…
  • comparison_tree_depthThe depth of a comparison decision tree is the maximum number of comparisons along any branch from the root to a leaf.
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.

The proof, explained

The claim is proved by structural induction on the comparison tree T. For a leaf, binding the continuation f yields f a while the leaf has depth 0, so the depth bound reduces immediately to the uniform bound d on continuation trees. For a branch, binding distributes recursively into both subtrees, expressing the composed depth as 1 plus the maximum of the two composed subtree depths. Applying the induction hypotheses to each subtree and using the monotonicity of addition over the maximum completes the bound.

  1. The depth bound holds when T is a leaf node.

    We proceed by structural induction on T. In the base case, T = ComparisonTree.leaf a. By the definition of tree binding (comparison_tree_bind.eq_1), comparison_tree_bind (ComparisonTree.leaf a) f evaluates to f a, and by comparison_tree_depth.eq_1, the depth of a leaf is 0. The inequality therefore simplifies to comparison_tree_depth (f a) ≤ 0 + d = d, which holds directly by the assumption h a that every continuation tree has depth at most d.

    lines 5–8

    uses comparison_tree_bind.eq_1, comparison_tree_depth.eq_1

      induction T with
      | leaf a =>
        rw [comparison_tree_bind.eq_1, comparison_tree_depth.eq_1]
        simpa using h a
  2. The depth bound holds when T is a branch node, completing the induction.

    For the inductive step, let T = ComparisonTree.branch i j l r, with induction hypotheses ih_l and ih_r bounding the depths of the composed left and right subtrees. Rewriting with comparison_tree_bind.eq_2 distributes the continuation binding over the branch, yielding ComparisonTree.branch i j (comparison_tree_bind l f) (comparison_tree_bind r f). Rewriting with comparison_tree_depth.eq_2 on both sides expresses the depths of both branch trees as 1 + max of the depths of their subtrees. The resulting inequality, 1 + max (comparison_tree_depth (comparison_tree_bind l f)) (comparison_tree_depth (comparison_tree_bind r f)) ≤ 1 + max (comparison_tree_depth l) (comparison_tree_depth r) + d, follows from the induction hypotheses by linear arithmetic (omega) since addition of d distributes over the maximum.

    lines 9–11

    uses comparison_tree_bind.eq_2, comparison_tree_depth.eq_2

      | branch i j l r ih_l ih_r =>
        rw [comparison_tree_bind.eq_2, comparison_tree_depth.eq_2, comparison_tree_depth.eq_2]
        omega
comparison_tree_bind.eq_1
Binding a family of continuation trees f to a leaf ComparisonTree.leaf a evaluates to f a.
comparison_tree_depth.eq_1
The comparison depth of a leaf node ComparisonTree.leaf ans is 0.
comparison_tree_bind.eq_2
Binding continuation trees f to a branch ComparisonTree.branch i j l r distributes the bind recursively over the left and right subtrees l and r.
comparison_tree_depth.eq_2
The depth of a branch ComparisonTree.branch i j l r is 1 plus the maximum of the depths of its left and right subtrees.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Depth of a composed tree is at most the depth of the first stage plus a uniform bound on the continuations. -/theorem comparison_tree_depth_bind_le {n : ℕ} (T : ComparisonTree n) (f : Fin n → ComparisonTree n)    (d : ℕ) (h : ∀ a, comparison_tree_depth (f a) ≤ d) :    comparison_tree_depth (comparison_tree_bind T f) ≤ comparison_tree_depth T + d := by  induction T with  | leaf a =>    rw [comparison_tree_bind.eq_1, comparison_tree_depth.eq_1]    simpa using h a  | branch i j l r ih_l ih_r =>    rw [comparison_tree_bind.eq_2, comparison_tree_depth.eq_2, comparison_tree_depth.eq_2]    omega
See it in the graphDiscuss this resultChallenge it