greedy_rc_step_sanity
With cm = id, one GREEDY-RC step on {12, 23} gives {123}.
Statement
theorem greedy_rc_step_sanity :
greedy_rc_step id ({[1, 2], [2, 3]} : Finset (List ℕ)) {[1, 2, 3]}- Source
- Sanity check of greedy_rc_step (arXiv:2611.16573)
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- greedy_rc_stepFor cm : Γ → Γ and S, S' : Finset (List Γ), greedy_rc_step cm S S' holds when S has more than one element and, with V = S ∪ rev_comp cm ''…
- string_overlap_lenFor two lists x, y : List Γ over an arbitrary alphabet type Γ with decidable equality (strings are lists of letters, not Lean Strings),…
- rev_compThe reverse complement rc(s) of a string s = a_1…a_m under a complement map cm is cm(a_m)…cm(a_1).
- string_overlap_mergeFor two lists x, y : List Γ over an alphabet type Γ with decidable equality, the overlap merge ⟨x,y⟩ is the list consisting of the first…
The proof, explained
This theorem is a concrete sanity check showing that a single GREEDY-RC step merges the set of lists $\{[1, 2], [2, 3]\}$ into $\{[1, 2, 3]\}$ under the identity complement map. Unfolding the definition reduces the claim to a bounded existential statement over finite sets of short lists. Because all operations—string overlap computation, set difference, and reverse-complementation—are finite and computable, the goal is verified by direct computation.
A single GREEDY-RC step with identity complementation transforms $\{[1, 2], [2, 3]\}$ into $\{[1, 2, 3]\}$. automation
Unfolding the definition of `greedy_rc_step` reduces the goal to checking that the initial set has size greater than 1, and that there is an eligible pair of strings in $\{[1, 2], [2, 3]\} \cup \{\operatorname{rev\_comp}(\operatorname{id}, [1, 2]), \operatorname{rev\_comp}(\operatorname{id}, [2, 3])\}$ with maximal overlap whose merger produces $[1, 2, 3]$. Since all domains, string operations, and set operations involved are finite and computable, the tactic `decide` verifies the condition by direct evaluation.
unfold greedy_rc_step; decide
- The entire verification is handled by Lean's computational kernel via `decide`, which evaluates the finite search over pairs of strings and their overlaps by computational reflection.
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.
theorem greedy_rc_step_sanity : greedy_rc_step id ({[1, 2], [2, 3]} : Finset (List ℕ)) {[1, 2, 3]} := by unfold greedy_rc_step; decide