AFTD Auto-Formalizing Theoretical Domains

comparison_tree_correct_for_selection

def

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