word_subtraction_language_N
For an alphabet α and a language S over α, word_subtraction_language_N S is the language of winning positions (N-positions) in the normal-play word subtraction game with subtraction set S, where a word w is an N-position if and only if there exist a word s in S and a prefix u such that w = u ++ s and u is not an N-position.
Statement
def word_subtraction_language_N {α : Type*} (S : Language α) : Language α
- Defined in
- arXiv:2611.09157 Definition 1.5
- Verified
- 10 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given a type α and a language S : Language α (that is, S : Set (List α)), word_subtraction_language_N S is the language of words w : List α defined by well-founded recursion on w.length as follows: a word w belongs to the language if and only if there exist a word s ∈ S, a word u : List α, and a proof h : u.length < w.length such that w = u ++ s and u does not belong to the language (evaluated recursively on u with proof h).
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 (N-positions) in the normal-play word subtraction game with subtraction set S. -/ def word_subtraction_language_N {α : Type*} (S : Language α) : Language α := { w | WellFounded.fix (measure List.length).wf (fun (w : List α) (rec : ∀ y, (measure List.length).rel y w → Prop) => ∃ s ∈ S, ∃ u : List α, ∃ (h : u.length < w.length), w = u ++ s ∧ ¬ rec u h) w }