AFTD Auto-Formalizing Theoretical Domains

word_subtraction_language_N

def

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 }
See it in the graphDiscuss this resultChallenge it