AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it