AFTD Auto-Formalizing Theoretical Domains

comparison_tree_correct_for_selection_exists

theoremverified

For every natural number n, strict partial order P on Fin n, and rank 1 ≤ i ≤ n, there exists a comparison decision tree on n elements that correctly selects the i-th smallest element for P.

Statement

theorem comparison_tree_correct_for_selection_exists {n : ℕ}
    (P : PartialOrder (Fin n)) (i : ℕ) (h1 : 1 ≤ i) (h2 : i ≤ n) :
    ∃ T : ComparisonTree n, comparison_tree_correct_for_selection n P i T
Source
arXiv:2610.18740 Section 5
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • comparison_tree_correct_for_selectionGiven a natural number n, a partial order P on Fin n, a rank i, and a comparison tree t on n elements, t correctly selects the i-th…
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
  • 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…
  • is_linear_extensionGiven a natural number n, a partial order P on Fin n, and a linear order L on Fin n, L is a linear extension of P if for all x y in Fin n,…

Read back from the Lean

For any natural number $n$, any partial order $P$ on $\mathrm{Fin}(n)$, and any natural number $i$ such that $1 \le i \le n$, there exists a comparison tree $T$ on $n$ elements that correctly selects the $i$-th element for every linear extension of $P$: that is, for every linear order $L$ on $\mathrm{Fin}(n)$ extending $P$, evaluating $T$ with the identity valuation on $\mathrm{Fin}(n)$ under the order $L$ returns an element of $\mathrm{Fin}(n)$ strictly greater than exactly $i - 1$ elements of $\mathrm{Fin}(n)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof witnesses the existential quantifier by constructing a trivial decision tree with a single leaf returning the index i - 1 in Fin n, making zero comparisons. Evaluating this leaf tree always yields i - 1, regardless of the linear extension. Since the strict order in the specification resolves to the standard ordering on Fin n, the number of elements strictly smaller than i - 1 is exactly i - 1, satisfying the required condition.

  1. i - 1 is strictly less than n, so it forms a valid index in Fin n, and we choose the comparison tree consisting of a single leaf returning this index.

    Since 1 ≤ i ≤ n, linear integer arithmetic (`omega`) ensures i - 1 < n. We provide the constant decision tree `ComparisonTree.leaf ⟨i - 1, hr⟩` as the witness for the existential quantifier.

    lines 5–6

      have hr : i - 1 < n := by omega
      refine ⟨ComparisonTree.leaf ⟨i - 1, hr⟩, ?_⟩
  2. For any linear extension L of P, evaluating the leaf tree yields the index ⟨i - 1, hr⟩, reducing the problem to counting elements strictly less than ⟨i - 1, hr⟩.

    Let L be an arbitrary linear extension of P. By definition of `comparison_tree_eval`, evaluating a leaf tree returns its stored value directly. Rewriting with this evaluation simplifies the goal to showing that the set of elements in Fin n strictly less than ⟨i - 1, hr⟩ has cardinality i - 1.

    lines 7–10

    uses comparison_tree_eval

      intro L hL
      have heval : comparison_tree_eval (fun a : Fin n => a) (ComparisonTree.leaf (⟨i - 1, hr⟩ : Fin n)) = ⟨i - 1, hr⟩ := by
        simp [comparison_tree_eval]
      rw [heval]
  3. The number of elements in Fin n strictly less than ⟨i - 1, hr⟩ in the canonical order is equal to its natural number value (⟨i - 1, hr⟩).val.

    The set of elements strictly less than ⟨i - 1, hr⟩ is identified by extensionality and `Finset.mem_Iio` as the lower open interval `Finset.Iio ⟨i - 1, hr⟩`. By `Fin.card_Iio`, the cardinality of this interval is precisely the value of ⟨i - 1, hr⟩ as a natural number.

    lines 11–17

    uses Finset.mem_Iio, Fin.card_Iio

      have hcard : (Finset.univ.filter (fun x : Fin n => x < (⟨i - 1, hr⟩ : Fin n))).card = (⟨i - 1, hr⟩ : Fin n).val := by
        have hset : (Finset.univ.filter (fun x : Fin n => x < (⟨i - 1, hr⟩ : Fin n))) =
            @Finset.Iio (Fin n) (@PartialOrder.toPreorder (Fin n) (@Fin.instPartialOrder n))
              (Fin.instLocallyFiniteOrderBot n) (⟨i - 1, hr⟩ : Fin n) := by
          ext x
          simp [Finset.mem_Iio]
        rw [hset, @Fin.card_Iio n (⟨i - 1, hr⟩ : Fin n)]
  4. The cardinality is equal to i - 1, completing the proof.

    Because the natural number value of ⟨i - 1, hr⟩ is definitionally i - 1, rewriting with the previously established cardinality `hcard` closes the goal.

    lines 18–19

      change (Finset.univ.filter (fun x : Fin n => x < (⟨i - 1, hr⟩ : Fin n))).card = i - 1
      rw [hcard]
comparison_tree_eval
Evaluation of a comparison decision tree: a leaf node immediately evaluates to its stored index, while a branch evaluates to the left or right subtree depending on the comparison between two elements.
Finset.mem_Iio
An element x belongs to the open interval Finset.Iio a if and only if x < a.
Fin.card_Iio
In Fin n with its canonical order, the number of elements strictly less than b is the natural number value of b.

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

/-- For any partial order and valid rank, there exists a comparison tree correctly selecting that rank. -/theorem comparison_tree_correct_for_selection_exists {n : ℕ}    (P : PartialOrder (Fin n)) (i : ℕ) (h1 : 1 ≤ i) (h2 : i ≤ n) :    ∃ T : ComparisonTree n, comparison_tree_correct_for_selection n P i T := by  have hr : i - 1 < n := by omega  refine ⟨ComparisonTree.leaf ⟨i - 1, hr⟩, ?_⟩  intro L hL  have heval : comparison_tree_eval (fun a : Fin n => a) (ComparisonTree.leaf (⟨i - 1, hr⟩ : Fin n)) = ⟨i - 1, hr⟩ := by    simp [comparison_tree_eval]  rw [heval]  have hcard : (Finset.univ.filter (fun x : Fin n => x < (⟨i - 1, hr⟩ : Fin n))).card = (⟨i - 1, hr⟩ : Fin n).val := by    have hset : (Finset.univ.filter (fun x : Fin n => x < (⟨i - 1, hr⟩ : Fin n))) =        @Finset.Iio (Fin n) (@PartialOrder.toPreorder (Fin n) (@Fin.instPartialOrder n))          (Fin.instLocallyFiniteOrderBot n) (⟨i - 1, hr⟩ : Fin n) := by      ext x      simp [Finset.mem_Iio]    rw [hset, @Fin.card_Iio n (⟨i - 1, hr⟩ : Fin n)]  change (Finset.univ.filter (fun x : Fin n => x < (⟨i - 1, hr⟩ : Fin n))).card = i - 1  rw [hcard]
See it in the graphDiscuss this resultChallenge it