AFTD Auto-Formalizing Theoretical Domains

arrows_pos_grundy_options_finite

theoremverified

For 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 finite.

Statement

theorem arrows_pos_grundy_options_finite {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (n : ℕ) (p : ArrowsPos V) :
    { m : ℕ | ∃ q, ArrowsLegalMove G p q ∧ m = arrows_pos_grundy G n q }.Finite
Source
Helper for arrows_parity_of_threads_le_two, arXiv:2610.15145 Theorem 10.3 / Corollary 10.4 (the induction in the proof of Theorem 10.3: every option has value (e-1) mod 2 or an option of value e mod 2), done directly on positions of T without the sum decomposition
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • arrows_pos_grundyThe 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…
  • 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…
  • 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…
Used by 1

The proof, explained

The proof shows that the set of Grundy values of the legal moves from p is finite by embedding it into a larger finite set. Because the vertex set V is finite, the set of all positions ArrowsPos V is finite, which implies that the range of the Grundy evaluation function across all positions is finite. The Grundy values of legal options form a subset of this range, and any subset of a finite set is finite.

  1. The type of positions `ArrowsPos V` is finite.

    Unfolding the definition of `ArrowsPos V` shows that a position is a subtype of functions `V → V → Bool` satisfying an asymmetry condition. Since the vertex set `V` is finite, the function space `V → V → Bool` is finite, and any subtype of a finite type is finite. Lean's typeclass synthesis (`infer_instance`) concludes that `ArrowsPos V` is finite.

    line 4

      have : Finite (ArrowsPos V) := by unfold ArrowsPos; infer_instance
  2. The set of Grundy values of legal moves from p is finite.

    The set of Grundy values reachable in one legal move from p is a subset of the full range of the Grundy function `q ↦ arrows_pos_grundy G n q` over all positions `q : ArrowsPos V`. By `Set.finite_range`, the range of any function with a finite domain is finite. Any value m attained by a legal move to some position q is in this range with witness q. Since a subset of a finite set is finite, the set of option Grundy values is finite.

    lines 5–6

    uses Set.finite_range

      exact (Set.finite_range (fun q : ArrowsPos V => arrows_pos_grundy G n q)).subset
        (by rintro _ ⟨q, -, rfl⟩; exact ⟨q, rfl⟩)
Set.finite_range
The range of a function defined on a finite domain is a finite set.

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

theorem arrows_pos_grundy_options_finite {V : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V)    [DecidableRel G.Adj] (n : ℕ) (p : ArrowsPos V) :    { m : ℕ | ∃ q, ArrowsLegalMove G p q ∧ m = arrows_pos_grundy G n q }.Finite := by  have : Finite (ArrowsPos V) := by unfold ArrowsPos; infer_instance  exact (Set.finite_range (fun q : ArrowsPos V => arrows_pos_grundy G n q)).subset    (by rintro _ ⟨q, -, rfl⟩; exact ⟨q, rfl⟩)
See it in the graphDiscuss this resultChallenge it