comparison_tree_selects_rank
def
A comparison decision tree T on n elements (T : ComparisonTree n) correctly selects the element of rank r : Fin n if for every permutation σ : Equiv.Perm (Fin n), applying σ to the index returned by evaluating T on σ equals r, that is, σ (comparison_tree_eval σ T) = r.
Statement
def comparison_tree_selects_rank {n : ℕ} (T : ComparisonTree n) (r : Fin n) : Prop
- Defined in
- scout/2610-18740-selecting-the-7th-smallest-of-16-elements-takes-exactly-28.md:Sec. 3
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 2
- 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…
- Used by 7
- v_selection_three_two_upper_boundThe 2nd smallest (the median) of 3 distinct elements can be found using at most 3 pairwise comparisons, that is, V_2(3) ≤ 3.
- comparison_tree_selects_rank_existsFor every n and every rank r : Fin n there exists a comparison decision tree on n elements that correctly selects the element of rank r.
- comparison_selection_complexityThe worst-case comparison complexity to select the element of rank r : Fin n among n elements, defined as the infimum of the depths of all…
- v_selection_le_iffFor any positive rank i ≤ n and bound d, the worst-case comparison complexity V_i(n) is at most d if and only if there exists a comparison…
- v_selection_16_8_le_28_iff_exists_treeThe worst-case comparison complexity of selecting the 8th smallest element among 16 elements is at most 28 (that is, V_8(16) ≤ 28) if and…
- not_comparison_tree_selects_rank_two_leaf_oneFor n = 2, the leaf comparison decision tree returning index 0 does not correctly select rank 1.
- comparison_tree_selects_rank_one_zeroFor n = 1, the single leaf comparison decision tree returning index 0 correctly selects rank 0.
Read back from the Lean
Given a natural number $n$, a comparison tree $T$ on $n$ elements, and an index/rank $r \in \operatorname{Fin} n$, the declaration defines the proposition that for every permutation $\sigma$ of $\operatorname{Fin} n$, applying $\sigma$ to the index in $\operatorname{Fin} n$ returned by evaluating $T$ on the input $\sigma$ equals $r$.
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 decision tree on n elements selects rank r if on every permutation of Fin n it returns the index whose value is r. -/ def comparison_tree_selects_rank {n : ℕ} (T : ComparisonTree n) (r : Fin n) : Prop := ∀ σ : Equiv.Perm (Fin n), σ (comparison_tree_eval σ T) = r