is_token_segmentation_singleton
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.
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.
unfold is_token_segmentation constructor
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.
· induction y with | nil => rfl | cons a t ih => simp [ih]
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.
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
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.
/-- 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