not_comparison_tree_selects_rank_two_leaf_one
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.
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)$.
uses
Equiv.reflintro h have h0 := h (Equiv.refl (Fin 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.
uses
comparison_tree_evalsimp [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.
- On line 6, `simp` simplifies the evaluation of the leaf tree under the identity permutation and closes the proof by recognizing that $0 = 1$ is false in $\mathrm{Fin}(2)$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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