comparison_tree_selects_rank_one_zero
For n = 1, the single leaf comparison decision tree returning index 0 correctly selects rank 0.
Statement
theorem comparison_tree_selects_rank_one_zero :
comparison_tree_selects_rank (ComparisonTree.leaf (0 : Fin 1)) (0 : Fin 1)- 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 leaf comparison tree on 1 element containing index 0 selects rank 0; that is, for every permutation σ of Fin 1, applying σ to the result of evaluating the leaf tree (ComparisonTree.leaf 0) on σ yields 0.
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 single-leaf tree on one element correctly selects rank 0, we introduce an arbitrary permutation σ of Fin 1. The goal is an equality between two elements of Fin 1. Because Fin 1 has only one element, any two of its terms are equal by subsingleton elimination.
Let σ be an arbitrary permutation of Fin 1.
By definition of `comparison_tree_selects_rank`, we must show that for any permutation σ of the inputs, σ applied to the evaluation of the tree yields rank 0. We introduce an arbitrary permutation σ.
intro σσ (comparison_tree_eval σ (ComparisonTree.leaf 0)) = 0
Both sides of the equation are elements of the type `Fin 1`. Because `Fin 1` has only a single element, it is a subsingleton, and any two of its terms are equal by `Subsingleton.elim`.
uses
Subsingleton.elimexact Subsingleton.elim _ _
Subsingleton.elim- In any type with at most one element (a subsingleton), any two terms are equal.
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 on 1 element selects rank 0. -/theorem comparison_tree_selects_rank_one_zero : comparison_tree_selects_rank (ComparisonTree.leaf (0 : Fin 1)) (0 : Fin 1) := by intro σ exact Subsingleton.elim _ _