AFTD Auto-Formalizing Theoretical Domains

bpe_partial_merge_disallows_overlaps

theoremverified

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.

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

    line 1

    uses bpe_partial_merge

    theorem 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

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

theorem bpe_partial_merge_disallows_overlaps : ¬ bpe_partial_merge 1 1 9 [1,1,1] [9,9] := by simp [bpe_partial_merge]
See it in the graphDiscuss this resultChallenge it