word_subtraction_N
For an alphabet α and a finite subtraction set S of lists over α, word_subtraction_N S is the language of winning positions (N-positions) in normal play, where a word w is winning if and only if there exist a word s in S and a prefix u such that w = u ++ s and u is not winning.
Statement
def word_subtraction_N {α : Type*} (S : Finset (List α)) : Language α
- Defined in
- arXiv:2611.09157 Section 1.3
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 1
- word_subtraction_invThe state invariant: the buffer is the reverse window of w, and for each j ≤ n the status bit j is true exactly when j exceeds the length…
Read back from the Lean
For a type α and a finite set of words S : Finset (List α), word_subtraction_N S is defined as the language (Set (List α)) of words w : List α satisfying a predicate defined by well-founded recursion on List.length: a word w belongs to word_subtraction_N S if and only if there exist s ∈ S, a word u : List α, and a proof h : u.length < w.length such that w = u ++ s and u does not satisfy the predicate (i.e., u ∉ word_subtraction_N S).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The language of winning positions in the normal-play word subtraction game with subtraction set S. -/ def word_subtraction_N {α : Type*} (S : Finset (List α)) : Language α := { w | WellFounded.fix (measure List.length).wf (fun w rec => ∃ s ∈ S, ∃ u : List α, ∃ (h : u.length < w.length), w = u ++ s ∧ ¬ rec u h) w }