AFTD Auto-Formalizing Theoretical Domains

comparison_tree_selects_rank_exists

theoremverified

For 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.

Statement

theorem comparison_tree_selects_rank_exists {n : ℕ} (r : Fin n) : ∃ T : ComparisonTree n, comparison_tree_selects_rank T r
Source
step towards v_selection_16_8_lower_bound
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • comparison_tree_selects_rankA comparison decision tree T on n elements (T : ComparisonTree n) correctly selects the element of rank r : Fin n if for every permutation…
  • 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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • 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…

The proof, explained

We construct an oblivious comparison decision tree that performs every pairwise comparison between elements of Fin n in sequence, recording the boolean outcomes in an accumulated matrix. At each leaf, a selection rule counts how many elements are smaller than each element according to the observed comparison table and outputs the unique element preceded by exactly r.val elements. When evaluated on any permutation σ, the accumulated table is the complete comparison matrix of σ, and the rank of σ⁻¹(r) under σ is precisely r, ensuring the tree correctly outputs the element of rank r.

  1. Every pair of elements p = (i, j) belongs to the list of all pairs.

    Decomposing p into (i, j), both coordinates belong to List.finRange n. Since comparison_tree_selects_rank_exists_all_pairs_list is defined as the Cartesian product of List.finRange n with itself, the pair belongs to the list.

    lines 6–7

    uses comparison_tree_selects_rank_exists_all_pairs_list

      rcases p with ⟨i, j⟩
      simp [comparison_tree_selects_rank_exists_all_pairs_list]
  2. Evaluating the decision tree constructed from query list L and accumulated matrix M on an input vector v equals applying the choice function to the matrix folded over L.

    By induction on L. When L is empty, the tree is a leaf returning choose M, matching the base foldl. For a list (i, j) :: tail, the tree branches on whether v i < v j; in each branch, entry (i, j) is set to the observed boolean outcome and the induction hypothesis equates subtree evaluation to the fold over the tail.

    lines 26–38

    uses comparison_tree_selects_rank_exists_build, comparison_tree_eval

      induction L generalizing M with
      | nil =>
        simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval]
      | cons head tail ih =>
        rcases head with ⟨i, j⟩
        simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval]
        split_ifs with h
        · rw [ih]
          have : decide (v i < v j) = true := by simp [h]
          rw [this]
        · rw [ih]
          have : decide (v i < v j) = false := by simp [h]
          rw [this]
  3. Folding comparison updates over list L produces a matrix whose entry at (i, j) is decide (v i < v j) if (i, j) ∈ L, and M i j otherwise.

    By induction on L. In the empty list case, (i, j) ∉ [] and the matrix is unchanged. For a step with head (x, y) and tail, the induction hypothesis applies to the tail: if (i, j) ∈ tail, the entry is already decide (v i < v j). If (i, j) ∉ tail, the entry comes from the update at (x, y), giving decide (v i < v j) when (i, j) = (x, y) and M i j otherwise.

    lines 44–56

    uses List.foldl_cons, List.mem_cons, comparison_tree_selects_rank_exists_update_matrix

      induction L generalizing M with
      | nil => simp
      | cons head tail ih =>
        rcases head with ⟨x, y⟩
        simp only [List.foldl_cons, ih, List.mem_cons]
        by_cases h : (i, j) ∈ tail
        · simp [h]
        · simp [h]
          dsimp [comparison_tree_selects_rank_exists_update_matrix]
          split_ifs with h2
          · rcases h2 with ⟨rfl, rfl⟩
            simp
          · simp
  4. When L contains every pair of indices, folding comparison updates over L yields the complete comparison matrix (i, j) ↦ decide (v i < v j).

    By function extensionality on (i, j), the folded matrix entry rewrites via comparison_tree_selects_rank_exists_foldl_update_matrix to a conditional check on (i, j) ∈ L. Since every pair belongs to L by assumption, the entry simplifies to decide (v i < v j).

    lines 62–64

    uses comparison_tree_selects_rank_exists_foldl_update_matrix

      ext i j
      rw [comparison_tree_selects_rank_exists_foldl_update_matrix]
      simp [hL (i, j)]
  5. For any permutation σ of Fin n and element a, the number of elements with smaller image under σ is (σ a).val.

    The set of elements b with σ b < σ a is the image under the embedding σ⁻¹ of the initial interval Finset.Iio (σ a). Embeddings preserve cardinality (Finset.card_map) and the interval of elements strictly below σ a has cardinality (σ a).val (Fin.card_Iio).

    lines 71–75

    uses Finset.card_map, Fin.card_Iio

      have h1 : Finset.filter (fun b => σ b < σ a) Finset.univ =
          (Finset.Iio (σ a)).map σ.symm.toEmbedding := by
        ext x
        simp
      rw [h1, Finset.card_map, Fin.card_Iio]
  6. Counting elements smaller than a in the boolean comparison matrix of σ equals (σ a).val.

    By definition, comparison_tree_selects_rank_exists_count_smaller counts elements b where decide (σ b < σ a) = true. This is equivalent to σ b < σ a, so the count equals the cardinality of the filtered set from comparison_tree_selects_rank_exists_card_filter_perm_lt, which is (σ a).val.

    lines 79–85

    uses comparison_tree_selects_rank_exists_count_smaller, comparison_tree_selects_rank_exists_card_filter_perm_lt

      dsimp [comparison_tree_selects_rank_exists_count_smaller]
      have h : (Finset.filter (fun b => decide (σ b < σ a) = true) Finset.univ) =
          (Finset.filter (fun b => σ b < σ a) Finset.univ) := by
        ext b
        simp
      rw [h]
      exact comparison_tree_selects_rank_exists_card_filter_perm_lt σ a
  7. Applying σ to the element selected by choose_rank r on σ's comparison matrix produces r.

    The selection function choose_rank r checks for an element with count r.val. The element a = σ⁻¹(r) is a valid witness since its count is (σ(σ⁻¹(r))).val = r.val. Given this witness, Classical.choose selects an element with count r.val, and by injectivity of Fin.val (Fin.ext), σ applied to that chosen element equals r.

    lines 92–101

    uses comparison_tree_selects_rank_exists_choose_rank, comparison_tree_selects_rank_exists_count_smaller_perm, dif_pos, Classical.choose_spec, Fin.ext

      dsimp [comparison_tree_selects_rank_exists_choose_rank]
      have h : ∃ a : Fin n, comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) a = r.val := by
        use σ.symm r
        rw [comparison_tree_selects_rank_exists_count_smaller_perm]
        simp
      rw [dif_pos h]
      have ha : comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) (Classical.choose h) = r.val :=
        Classical.choose_spec h
      rw [comparison_tree_selects_rank_exists_count_smaller_perm] at ha
      exact Fin.ext ha
  8. We construct the candidate decision tree T that queries all pairs and fix an arbitrary permutation σ of Fin n.

    We instantiate the leaf selector with comparison_tree_selects_rank_exists_choose_rank r and build tree T by querying all pairs in comparison_tree_selects_rank_exists_all_pairs_list n starting from an initial all-false matrix. We then fix an arbitrary permutation σ.

    lines 105–109

      let choose := comparison_tree_selects_rank_exists_choose_rank r
      let T := comparison_tree_selects_rank_exists_build choose (comparison_tree_selects_rank_exists_all_pairs_list n) (fun _ _ => false)
      use T
      intro σ
      dsimp [T, choose]
  9. Evaluating T on σ correctly selects the element of rank r.

    Evaluating T on σ rewrites via comparison_tree_selects_rank_exists_build_eval to running the leaf selector on the matrix folded over all pairs. Because every pair is in the list, this fold yields the complete comparison matrix of σ (comparison_tree_selects_rank_exists_foldl_update_matrix_all). Finally, comparison_tree_selects_rank_exists_choose_rank_spec guarantees that σ of the selected element equals r.

    lines 110–113

    uses comparison_tree_selects_rank_exists_build_eval, comparison_tree_selects_rank_exists_foldl_update_matrix_all, comparison_tree_selects_rank_exists_mem_all_pairs_list, comparison_tree_selects_rank_exists_choose_rank_spec

      rw [comparison_tree_selects_rank_exists_build_eval]
      rw [comparison_tree_selects_rank_exists_foldl_update_matrix_all (⇑σ) (comparison_tree_selects_rank_exists_all_pairs_list n)
        comparison_tree_selects_rank_exists_mem_all_pairs_list]
      exact comparison_tree_selects_rank_exists_choose_rank_spec r σ
Classical.choose_spec
The witness produced by Classical.choose satisfies the existential predicate.
Fin.card_Iio
The number of elements in Fin n strictly less than b is equal to the numerical value of b.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Finset.card_map
The cardinality of a finite set is preserved under mapping by an embedding.
List.foldl_cons
Folding a function over a cons list equals folding over the tail starting from the function applied to the initial accumulator and the head element.
List.mem_cons
An element belongs to a non-empty list if and only if it equals the head or belongs to the tail.
comparison_tree_eval
Evaluates a comparison decision tree on an input vector v by following the branches dictated by the comparisons until reaching a leaf.
comparison_tree_selects_rank_exists_all_pairs_list
The list of all pairs in Fin n × Fin n, defined as the Cartesian product of List.finRange n with itself.
comparison_tree_selects_rank_exists_build
Recursively builds a comparison decision tree that queries each pair in a list in order, updating an accumulated boolean matrix at each branch until reaching leaves.
comparison_tree_selects_rank_exists_build_eval
Evaluating the tree built from a query list on an input vector v applies the choice function to the matrix accumulated by folding comparison updates over the list.
comparison_tree_selects_rank_exists_card_filter_perm_lt
For any permutation σ of Fin n and element a, exactly (σ a).val elements have a strictly smaller image under σ.
comparison_tree_selects_rank_exists_choose_rank
Selects an element whose count of smaller elements in matrix M is r.val if one exists, defaulting to r otherwise.
comparison_tree_selects_rank_exists_choose_rank_spec
Applying the permutation σ to the element chosen by choose_rank from the comparison matrix of σ yields the target rank r.
comparison_tree_selects_rank_exists_count_smaller
The number of elements b in Fin n for which M b a is true in a boolean comparison matrix M.
comparison_tree_selects_rank_exists_count_smaller_perm
Counting the elements smaller than a in the boolean comparison matrix of a permutation σ returns (σ a).val.
comparison_tree_selects_rank_exists_foldl_update_matrix
Folding comparison updates over a list L yields a matrix whose entry at (i, j) is decide (v i < v j) if (i, j) ∈ L, and M i j otherwise.
comparison_tree_selects_rank_exists_foldl_update_matrix_all
When L contains every pair of indices, folding comparison updates over L yields the complete comparison matrix (i, j) ↦ decide (v i < v j).
comparison_tree_selects_rank_exists_mem_all_pairs_list
Every pair of indices in Fin n × Fin n is an element of the list of all pairs.
comparison_tree_selects_rank_exists_update_matrix
Updates a boolean matrix by setting the entry at (i, j) to a given boolean while leaving all other entries unchanged.
dif_pos
A dependent if-then-else expression evaluates to its 'then' branch when the condition is proven.

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

def comparison_tree_selects_rank_exists_all_pairs_list (n : ℕ) : List (Fin n × Fin n) :=  (List.finRange n).product (List.finRange n)lemma comparison_tree_selects_rank_exists_mem_all_pairs_list {n : ℕ} (p : Fin n × Fin n) :    p ∈ comparison_tree_selects_rank_exists_all_pairs_list n := by  rcases p with ⟨i, j⟩  simp [comparison_tree_selects_rank_exists_all_pairs_list]def comparison_tree_selects_rank_exists_update_matrix {n : ℕ} (M : Fin n → Fin n → Bool) (i j : Fin n) (b : Bool) :    Fin n → Fin n → Bool :=  fun x y => if x = i ∧ y = j then b else M x ydef comparison_tree_selects_rank_exists_build {n : ℕ} (choose : (Fin n → Fin n → Bool) → Fin n) :    List (Fin n × Fin n) → (Fin n → Fin n → Bool) → ComparisonTree n  | [], M => ComparisonTree.leaf (choose M)  | (i, j) :: rest, M =>    ComparisonTree.branch i j      (comparison_tree_selects_rank_exists_build choose rest (comparison_tree_selects_rank_exists_update_matrix M i j true))      (comparison_tree_selects_rank_exists_build choose rest (comparison_tree_selects_rank_exists_update_matrix M i j false))theorem comparison_tree_selects_rank_exists_build_eval {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α)    (choose : (Fin n → Fin n → Bool) → Fin n)    (L : List (Fin n × Fin n)) (M : Fin n → Fin n → Bool) :    comparison_tree_eval v (comparison_tree_selects_rank_exists_build choose L M) =      choose (L.foldl (fun m p => comparison_tree_selects_rank_exists_update_matrix m p.1 p.2 (decide (v p.1 < v p.2))) M) := by  induction L generalizing M with  | nil =>    simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval]  | cons head tail ih =>    rcases head with ⟨i, j⟩    simp [comparison_tree_selects_rank_exists_build, comparison_tree_eval]    split_ifs with h    · rw [ih]      have : decide (v i < v j) = true := by simp [h]      rw [this]    · rw [ih]      have : decide (v i < v j) = false := by simp [h]      rw [this]lemma comparison_tree_selects_rank_exists_foldl_update_matrix {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α)    (L : List (Fin n × Fin n)) (M : Fin n → Fin n → Bool) (i j : Fin n) :    (L.foldl (fun m p => comparison_tree_selects_rank_exists_update_matrix m p.1 p.2 (decide (v p.1 < v p.2))) M) i j =      if (i, j) ∈ L then decide (v i < v j) else M i j := by  induction L generalizing M with  | nil => simp  | cons head tail ih =>    rcases head with ⟨x, y⟩    simp only [List.foldl_cons, ih, List.mem_cons]    by_cases h : (i, j) ∈ tail    · simp [h]    · simp [h]      dsimp [comparison_tree_selects_rank_exists_update_matrix]      split_ifs with h2      · rcases h2 with ⟨rfl, rfl⟩        simp      · simplemma comparison_tree_selects_rank_exists_foldl_update_matrix_all {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α)    (L : List (Fin n × Fin n)) (hL : ∀ p, p ∈ L) (M : Fin n → Fin n → Bool) :    (L.foldl (fun m p => comparison_tree_selects_rank_exists_update_matrix m p.1 p.2 (decide (v p.1 < v p.2))) M) =      fun i j => decide (v i < v j) := by  ext i j  rw [comparison_tree_selects_rank_exists_foldl_update_matrix]  simp [hL (i, j)]def comparison_tree_selects_rank_exists_count_smaller {n : ℕ} (M : Fin n → Fin n → Bool) (a : Fin n) : ℕ :=  (Finset.filter (fun b => M b a = true) Finset.univ).cardlemma comparison_tree_selects_rank_exists_card_filter_perm_lt {n : ℕ} (σ : Equiv.Perm (Fin n)) (a : Fin n) :    (Finset.filter (fun b => σ b < σ a) Finset.univ).card = (σ a).val := by  have h1 : Finset.filter (fun b => σ b < σ a) Finset.univ =      (Finset.Iio (σ a)).map σ.symm.toEmbedding := by    ext x    simp  rw [h1, Finset.card_map, Fin.card_Iio]lemma comparison_tree_selects_rank_exists_count_smaller_perm {n : ℕ} (σ : Equiv.Perm (Fin n)) (a : Fin n) :    comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) a = (σ a).val := by  dsimp [comparison_tree_selects_rank_exists_count_smaller]  have h : (Finset.filter (fun b => decide (σ b < σ a) = true) Finset.univ) =      (Finset.filter (fun b => σ b < σ a) Finset.univ) := by    ext b    simp  rw [h]  exact comparison_tree_selects_rank_exists_card_filter_perm_lt σ anoncomputable def comparison_tree_selects_rank_exists_choose_rank {n : ℕ} (r : Fin n) (M : Fin n → Fin n → Bool) : Fin n :=  if h : ∃ a : Fin n, comparison_tree_selects_rank_exists_count_smaller M a = r.val then Classical.choose h else rlemma comparison_tree_selects_rank_exists_choose_rank_spec {n : ℕ} (r : Fin n) (σ : Equiv.Perm (Fin n)) :    σ (comparison_tree_selects_rank_exists_choose_rank r (fun b a => decide (σ b < σ a))) = r := by  dsimp [comparison_tree_selects_rank_exists_choose_rank]  have h : ∃ a : Fin n, comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) a = r.val := by    use σ.symm r    rw [comparison_tree_selects_rank_exists_count_smaller_perm]    simp  rw [dif_pos h]  have ha : comparison_tree_selects_rank_exists_count_smaller (fun b a => decide (σ b < σ a)) (Classical.choose h) = r.val :=    Classical.choose_spec h  rw [comparison_tree_selects_rank_exists_count_smaller_perm] at ha  exact Fin.ext ha/-- Every rank-selection problem is solvable by some comparison decision tree, so the set of depths used in `comparison_selection_complexity` is nonempty. -/theorem comparison_tree_selects_rank_exists {n : ℕ} (r : Fin n) : ∃ T : ComparisonTree n, comparison_tree_selects_rank T r := by  let choose := comparison_tree_selects_rank_exists_choose_rank r  let T := comparison_tree_selects_rank_exists_build choose (comparison_tree_selects_rank_exists_all_pairs_list n) (fun _ _ => false)  use T  intro σ  dsimp [T, choose]  rw [comparison_tree_selects_rank_exists_build_eval]  rw [comparison_tree_selects_rank_exists_foldl_update_matrix_all (⇑σ) (comparison_tree_selects_rank_exists_all_pairs_list n)    comparison_tree_selects_rank_exists_mem_all_pairs_list]  exact comparison_tree_selects_rank_exists_choose_rank_spec r σ
See it in the graphDiscuss this resultChallenge it