AFTD Auto-Formalizing Theoretical Domains

arrows_pos_grundy

def

The Grundy value of a position p : ArrowsPos V in the Game of Arrows on G at recursion depth fuel, defined as 0 when fuel = 0 and as the minimum excluded natural number (nat_mex_set) of the values of legal moves q at depth fuel' when fuel = fuel' + 1.

Statement

noncomputable def arrows_pos_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (fuel : ℕ) (p : ArrowsPos V) : ℕ
Defined in
arXiv:2610.15145 Section 2.2
Verified
24 Oct 2026
Axioms
none listed
Built on 3
  • ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
  • ArrowsLegalMoveIn a simple graph G, a transition from position p to q in ArrowsPos V is a legal move if there exist u, v with ArrowsUnmarked G p u v such…
  • nat_mex_setThe minimum excluded natural number of a set s of natural numbers is the infimum of the set of natural numbers not in s.
Used by 3
  • arrows_pos_grundy_eq_mod_two_of_classStrategy lemma for parity in the Game of Arrows: let e be a function on positions that drops by exactly one along every legal move, and S…
  • arrows_tree_grundyThe Grundy value of the Game of Arrows on a finite simple graph G is the Grundy value of the empty position ArrowsEmptyPos V at fuel…
  • arrows_pos_grundy_options_finiteFor any fuel and position p of the Game of Arrows on a finite graph, the set of fuel-bounded Grundy values of the legal options of p is…

Read back from the Lean

arrows_pos_grundy is a function that, given a type V with decidable equality and a Fintype instance, a simple graph G on V with decidable adjacency, a recursion depth bound fuel : ℕ, and a partial orientation p : ArrowsPos V, recursively computes a natural number (the Grundy / mex-value bounded by fuel) as follows: - When fuel = 0, it returns 0. - When fuel = fuel' + 1, it returns the minimum excluded natural number (nat_mex_set) of the set of values arrows_pos_grundy G fuel' q over all positions q : ArrowsPos V such that ArrowsLegalMove G p q holds.

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 Grundy value of a Game of Arrows position p under fuel recursion, using the minimum excluded value over all legal moves. -/
noncomputable def arrows_pos_grundy {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (fuel : ℕ) (p : ArrowsPos V) : ℕ := match fuel with
  | 0 => 0
  | fuel + 1 => nat_mex_set { n : ℕ | ∃ q, ArrowsLegalMove G p q ∧ n = arrows_pos_grundy G fuel q }
See it in the graphDiscuss this resultChallenge it