comparison_tree_correct_for_selection
Given 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 smallest element for P if for every linear extension L of P on Fin n, evaluating t under L yields an element of Fin n with exactly i - 1 elements strictly smaller than it under L.
Statement
def comparison_tree_correct_for_selection (n : ℕ) (P : PartialOrder (Fin n)) (i : ℕ) (t : ComparisonTree n) : Prop
- Defined in
- arXiv:2610.18740 Section 5
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 3
- 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,…
- Used by 2
- v_selection_posetFor a natural number n, a partial order P on Fin n, and a rank i, V_i(P) is the infimum of depths of all comparison decision trees on n…
- comparison_tree_correct_for_selection_existsFor 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…
Read back from the Lean
The definition comparison_tree_correct_for_selection n P i t asserts that:
For all linear orders L on Fin n, if L is a linear extension of P (that is, for all x y : Fin n, x ≤ y under P implies x ≤ y under L), then the evaluation of the comparison tree t on the identity map (comparing elements of Fin n using the strict order < of L) produces an element ans : Fin n such that the number of elements x : Fin n satisfying x < ans under L is exactly i - 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A comparison tree on Fin n correctly selects the i-th smallest element under all linear extensions. -/ def comparison_tree_correct_for_selection (n : ℕ) (P : PartialOrder (Fin n)) (i : ℕ) (t : ComparisonTree n) : Prop := open scoped Classical in ∀ (L : LinearOrder (Fin n)), is_linear_extension P L → letI := L (Finset.filter (fun x => x < comparison_tree_eval (fun a => a) t) Finset.univ).card = i - 1