AFTD Auto-Formalizing Theoretical Domains

comparison_tree_selects_rank_one_zero

theoremverified

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.

  1. 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 σ.

    line 4

      intro σ
  2. σ (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`.

    line 5

    uses Subsingleton.elim

      exact 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

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