string_overlap_merge_sanity
⟨123, 234⟩ = 1234.
Statement
theorem string_overlap_merge_sanity :
string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4]- Source
- Sanity check of string_overlap_merge (arXiv:2611.16573)
- Verified
- 14 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 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
The theorem verifies as a sanity check that merging the lists `[1, 2, 3]` and `[2, 3, 4]` yields `[1, 2, 3, 4]`. Because the inputs are concrete lists and all functions involved are fully computable, the statement is proved by direct computation using the `decide` tactic.
string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4] automation
Both lists and all operations in `string_overlap_merge`—length calculation, bounded linear search for the greatest overlap length, list dropping, taking, and concatenation—are computable for concrete lists of natural numbers. The maximal proper overlap between `[1, 2, 3]` and `[2, 3, 4]` is `[2, 3]` (length 2), so the first list is trimmed to its first `3 - 2 = 1` element (`[1]`) and concatenated with `[2, 3, 4]`, yielding `[1, 2, 3, 4]`. The `decide` tactic performs this finite computation directly to close the goal.
string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4] := by decide
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 string_overlap_merge_sanity : string_overlap_merge [1, 2, 3] [2, 3, 4] = [1, 2, 3, 4] := by decide