AFTD Auto-Formalizing Theoretical Domains

not_comparison_tree_selects_rank_two_leaf_one

theoremverified

For n = 2, the leaf comparison decision tree returning index 0 does not correctly select rank 1.

Statement

theorem not_comparison_tree_selects_rank_two_leaf_one :
    ¬ comparison_tree_selects_rank (ComparisonTree.leaf (0 : Fin 2)) (1 : Fin 2)
Source
scout/2610-18740-selecting-the-7th-smallest-of-16-elements-takes-exactly-28.md:Sec. 3
Verified
18 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • 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…
  • 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…

Read back from the Lean

The comparison tree consisting of a single leaf returning index 0 : Fin 2 does not select rank 1 : Fin 2 according to comparison_tree_selects_rank.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that the leaf tree returning index 0 does not select rank 1 for $n = 2$, we proceed by contradiction. By definition, selecting rank 1 requires every permutation $\sigma$ to satisfy $\sigma(\mathrm{eval}(\sigma, T)) = 1$. Specializing this requirement to the identity permutation forces $0 = 1$ in $\mathrm{Fin}(2)$, an immediate contradiction.

  1. Under the assumption that the tree selects rank 1, applying the identity permutation to the tree's evaluation must yield 1.

    We argue by contradiction and assume that the leaf tree selects rank 1, which by definition means that $\sigma(\mathrm{eval}(\sigma, T)) = 1$ for every permutation $\sigma$ of $\mathrm{Fin}(2)$. We then specialize this universal assumption to the identity permutation $\sigma = \mathrm{Equiv.refl}(\mathrm{Fin}\,2)$.

    lines 4–5

    uses Equiv.refl

      intro h
      have h0 := h (Equiv.refl (Fin 2))
  2. A contradiction ($0 = 1$) is reached, completing the proof. automation

    By the definition of `comparison_tree_eval`, a leaf node returning 0 evaluates to 0 regardless of the input. Because the identity permutation fixes 0, the equation reduces to $0 = 1$ in $\mathrm{Fin}(2)$, which is impossible.

    line 6

    uses comparison_tree_eval

      simp [comparison_tree_eval] at h0
Equiv.refl
The identity bijection from a type to itself, which leaves every element unchanged.
comparison_tree_eval
Evaluates a comparison decision tree on an input vector; on a leaf node, it directly returns the leaf's stored index.

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

/-- The leaf comparison tree returning 0 on 2 elements does not select rank 1. -/theorem not_comparison_tree_selects_rank_two_leaf_one :    ¬ comparison_tree_selects_rank (ComparisonTree.leaf (0 : Fin 2)) (1 : Fin 2) := by  intro h  have h0 := h (Equiv.refl (Fin 2))  simp [comparison_tree_eval] at h0
See it in the graphDiscuss this resultChallenge it