AFTD Auto-Formalizing Theoretical Domains

bpe_zero_step_run_unique

theoremverified

A zero-step greedy Byte-Pair Encoding run from string s to string t holds if and only if s = t.

Statement

theorem bpe_zero_step_run_unique (s t : List ℕ) :
    bpe_greedy_run 0 s t ↔ s = t
Source
knowledgebase, supporting OP-1533
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • bpe_greedy_runThe relation defining a k-step greedy Byte-Pair Encoding run on string s yielding string t: for k = 0 we have s = t, and for k + 1 there…

Read back from the Lean

For all lists of natural numbers $s$ and $t$, a 0-step greedy BPE run transforms $s$ into $t$ if and only if $s = t$.

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

The theorem states that a zero-step greedy Byte-Pair Encoding run from string s to string t holds if and only if s = t. The proof proceeds by unfolding the definition of `bpe_greedy_run`, whose base case for zero steps is defined directly as the equality s = t. This reduces the statement to the trivial equivalence s = t ↔ s = t.

  1. A zero-step greedy BPE run from s to t is equivalent to s = t.

    By definition of `bpe_greedy_run`, a zero-step run `bpe_greedy_run 0 s t` is defined directly as `s = t`. The simplifier unfolds this definition, reducing the equivalence to `s = t ↔ s = t`, which simplifies to true by propositional logic.

    line 4

    uses bpe_greedy_run

      simp [bpe_greedy_run]
bpe_greedy_run
The definition of a k-step greedy BPE execution; for 0 steps, bpe_greedy_run 0 s t is defined as s = t.

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

/-- A zero-step greedy BPE run leaves the string identical. -/theorem bpe_zero_step_run_unique (s t : List ℕ) :    bpe_greedy_run 0 s t ↔ s = t := by  simp [bpe_greedy_run]
See it in the graphDiscuss this resultChallenge it