AFTD Auto-Formalizing Theoretical Domains

comparison_tree_eval_bind

theoremverified

Running the composition comparison_tree_bind T f on a value assignment v gives the same index as running T on v and then running the continuation tree f on the index that T returned.

Statement

theorem comparison_tree_eval_bind {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α)
    (T : ComparisonTree n) (f : Fin n → ComparisonTree n) :
    comparison_tree_eval v (comparison_tree_bind T f)
      = comparison_tree_eval v (f (comparison_tree_eval v T))
Source
step towards v_selection_16_8_upper_bound
Verified
19 Oct 2026
Axioms
propext
Built on 5
  • 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_evalGiven an assignment v : Fin n → α of values in a linearly ordered type α, evaluate a comparison tree: on a leaf leaf ans, return the index…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

The proof proceeds by structural induction on the comparison tree $T$. For a leaf, tree composition immediately applies the continuation function to the leaf's stored index, making the identity hold by definition. For an internal branch node, unfolding the definitions of composition and evaluation reveals that both sides branch on the same comparison; case splitting on that comparison reduces each case directly to the inductive hypothesis for the corresponding subtree.

  1. The theorem holds when $T$ is a leaf node $\text{leaf}(a)$.

    We proceed by structural induction on $T$. In the base case where $T = \text{leaf}(a)$, both sides reduce definitionally to $\text{comparison\_tree\_eval}~v~(f~a)$, because binding a leaf simply yields $f~a$ and evaluating a leaf directly returns its stored value $a$. The equality therefore holds by reflexivity.

    lines 6–7

      induction T with
      | leaf a => rfl
  2. The theorem holds for branch nodes $\text{branch}(i, j, l, r)$ assuming it holds for subtrees $l$ and $r$.

    For an internal node comparing inputs at indices $i$ and $j$, unfolding the definitions of `comparison_tree_bind` and `comparison_tree_eval` expresses both sides as conditional expressions branching on whether $v(i) < v(j)$. Performing a case split on this comparison condition yields two goals: when $v(i) < v(j)$ is true, both sides evaluate along the left branch, which matches the inductive hypothesis `ihl` for $l$; when false, both sides evaluate along the right branch, which matches the inductive hypothesis `ihr` for $r$.

    lines 8–12

    uses comparison_tree_bind, comparison_tree_eval

      | branch i j l r ihl ihr =>
        simp only [comparison_tree_bind, comparison_tree_eval]
        split
        · exact ihl
        · exact ihr
comparison_tree_bind
The composition (or bind) operation for comparison trees, which replaces each leaf node carrying index `a` with the tree `f a`, leaving branching decisions unchanged.
comparison_tree_eval
Evaluates a comparison tree under an input valuation `v`, recursively branching on whether `v i < v j` until reaching a leaf and returning its index.

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

/-- Evaluation of a composed tree: running `bind T f` is running `T` and then continuing with the branch selected by its answer. -/theorem comparison_tree_eval_bind {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α)    (T : ComparisonTree n) (f : Fin n → ComparisonTree n) :    comparison_tree_eval v (comparison_tree_bind T f)      = comparison_tree_eval v (f (comparison_tree_eval v T)) := by  induction T with  | leaf a => rfl  | branch i j l r ihl ihr =>    simp only [comparison_tree_bind, comparison_tree_eval]    split    · exact ihl    · exact ihr
See it in the graphDiscuss this resultChallenge it