arrows_pos_grundy_options_finite
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
- 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…
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.
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.
have : Finite (ArrowsPos V) := by unfold ArrowsPos; infer_instance
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.
uses
Set.finite_rangeexact (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.
- The finiteness of `ArrowsPos V` is established via typeclass synthesis (`infer_instance`), which automatically combines the finiteness of the vertex type `V`, function spaces over finite domains, and subtypes.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩)