AFTD Auto-Formalizing Theoretical Domains

is_token_segmentation_singleton

theoremverified

Every word y admits a valid token segmentation into singletons over any vocabulary V.

Statement

theorem is_token_segmentation_singleton {α : Type*} (V : Set (List α)) (y : List α) :
    is_token_segmentation V y (y.map (fun c => [c]))
Source
arXiv:2611.15074, Section 2.1
Verified
14 Nov 2026
Axioms
Quot.soundpropext
Built on 1
  • is_token_segmentationA list of tokens forms a valid segmentation of a word y over vocabulary V and single-character alphabet if their concatenation is y and…

Read back from the Lean

For any type α, any set V of lists of α, and any list y of elements of α, the list of singletons formed by each element of y (y.map (fun c => [c])) is a token segmentation of y with respect to V.

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 wrapping every character of a word $y$ into a singleton list forms a valid token segmentation of $y$ over any vocabulary $V$. By definition of `is_token_segmentation`, this requires two properties: flattening the token list reconstructs $y$, and each token is either in $V$ or has length 1. The first property is proved by induction on $y$, while the second holds because each token is constructed as a singleton list $[c]$, which trivially has length 1.

  1. It suffices to show two conditions: flattening the list of singleton tokens yields $y$, and every token is either in $V$ or has length $1$.

    Unfolding the definition of `is_token_segmentation` expresses the proposition as a conjunction: `(y.map (fun c => [c])).flatten = y` and `∀ t ∈ y.map (fun c => [c]), t ∈ V ∨ t.length = 1`. Splitting the conjunction yields two separate subgoals.

    lines 4–5

      unfold is_token_segmentation
      constructor
  2. Flattening the list of singleton tokens reconstructs $y$.

    By induction on the list $y$. When $y$ is empty (`nil`), both sides simplify to the empty list by definition. In the inductive step where $y = a :: t$, mapping produces `[a] :: t.map (fun c => [c])`; flattening this yields `[a] ++ (t.map (fun c => [c])).flatten`, which simplifies to `a :: t` by rewriting with the induction hypothesis.

    lines 6–8

      · induction y with
        | nil => rfl
        | cons a t ih => simp [ih]
  3. Every token in the list of singletons satisfies the condition of having length $1$.

    Let $t$ be a token in `y.map (fun c => [c])`. Rewriting with `List.mem_map` shows that $t = [c]$ for some character $c \in y$. Selecting the right-hand alternative of the disjunction ($t \in V \lor t.\text{length} = 1$), the goal reduces to showing that $[c]$ has length $1$, which holds by definition.

    lines 9–13

    uses List.mem_map

      · intro t ht
        rw [List.mem_map] at ht
        obtain ⟨c, _, rfl⟩ := ht
        right
        simp
List.mem_map
An element belongs to the mapped list `List.map f l` if and only if it equals `f a` for some element `a ∈ l`.

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

/-- Sanity lemma: partitioning into singletons is a valid token segmentation. -/theorem is_token_segmentation_singleton {α : Type*} (V : Set (List α)) (y : List α) :    is_token_segmentation V y (y.map (fun c => [c])) := by  unfold is_token_segmentation  constructor  · induction y with    | nil => rfl    | cons a t ih => simp [ih]  · intro t ht    rw [List.mem_map] at ht    obtain ⟨c, _, rfl⟩ := ht    right    simp
See it in the graphDiscuss this resultChallenge it