comparison_tree_correct_for_selection_exists
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.
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.
have hr : i - 1 < n := by omega refine ⟨ComparisonTree.leaf ⟨i - 1, hr⟩, ?_⟩
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.
uses
comparison_tree_evalintro 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]
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.
uses
Finset.mem_Iio,Fin.card_Iiohave 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)]
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.
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.
- In the definition of `comparison_tree_correct_for_selection`, the inequality `<` in `{x | x < ...}` resolves to the canonical order on `Fin n` rather than the linear extension `L` introduced by `letI := L`. As a result, the correctness condition asks for the rank in the standard order of `Fin n`, allowing a trivial leaf tree without comparisons to satisfy the theorem.
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
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.
/-- 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]