bpe_partial_merge_disallows_overlaps
Two overlapping adjacent occurrences in a three-symbol run cannot both be merged.
Statement
theorem bpe_partial_merge_disallows_overlaps : ¬ bpe_partial_merge 1 1 9 [1,1,1] [9,9]- Source
- Sanity check for the partial merge relation in OP-1288.
- Verified
- 10 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- bpe_partial_mergeThe relation between input and output strings obtained by replacing an arbitrary subset of pairwise nonoverlapping occurrences of the…
The proof, explained
The theorem states that overlapping adjacent pairs in the sequence [1, 1, 1] cannot both be merged into 9s to yield [9, 9]. Merging the first two 1s into 9 consumes both occurrences, leaving only a single 1, which is not enough to form a second pair. Unfolding the recursive definition of bpe_partial_merge reduces both possible execution branches to contradictions, showing that the relation is false.
The relation bpe_partial_merge 1 1 9 [1, 1, 1] [9, 9] is false, which establishes its negation. automation
Evaluating the definition of bpe_partial_merge 1 1 9 [1, 1, 1] [9, 9] gives two cases for the first step: 1. The first symbol is kept unmerged: the output list must begin with 1, which contradicts the target list [9, 9] beginning with 9 (since 9 ≠ 1). 2. The first two symbols 1, 1 are merged into 9: the output list begins with 9, leaving the remaining input list [1] and requiring the remaining output to be [9]. However, on any singleton list [x], the definition mandates that the output must be [x] itself, which requires [9] = [1] (again impossible since 9 ≠ 1). Because both branches are contradictory, the relation evaluates to False, and the negation is proven.
uses
bpe_partial_mergetheorem bpe_partial_merge_disallows_overlaps : ¬ bpe_partial_merge 1 1 9 [1,1,1] [9,9] := by simp [bpe_partial_merge]
bpe_partial_merge- the relation defining when an output list is obtained from an input list by optionally replacing adjacent pairs of symbols equal to (a, b) with z
- The single tactic `simp [bpe_partial_merge]` automatically unfolds the recursive definition of `bpe_partial_merge` on the concrete lists and evaluates all resulting equalities of natural numbers and lists to false.
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 bpe_partial_merge_disallows_overlaps : ¬ bpe_partial_merge 1 1 9 [1,1,1] [9,9] := by simp [bpe_partial_merge]