AFTD Auto-Formalizing Theoretical Domains

arrows_pos_grundy_eq_mod_two_of_class

theoremverified

Strategy 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 a class of positions such that from every position in S with e >= 1 some legal move stays in S, and every legal move from a position in S lands in S or admits a legal reply back into S. Then every position p in S has fuel-bounded Grundy value e(p) mod 2 at every fuel greater than e(p).

Statement

theorem arrows_pos_grundy_eq_mod_two_of_class {V : Type*} [DecidableEq V] [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (S : ArrowsPos V → Prop) (e : ArrowsPos V → ℕ)
    (he : ∀ p q, ArrowsLegalMove G p q → e q + 1 = e p)
    (hex : ∀ p, S p → 1 ≤ e p → ∃ q, ArrowsLegalMove G p q ∧ S q)
    (hcl : ∀ p q, S p → ArrowsLegalMove G p q → S q ∨ ∃ r, ArrowsLegalMove G q r ∧ S r) :
    ∀ fuel p, S p → e p < fuel → arrows_pos_grundy G fuel p = e p % 2
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 8
  • 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…
  • nat_mex_set_eq_zero_of_not_memIf 0 is not in a set s of natural numbers, the mex of s is 0.
  • nat_mex_set_eq_one_of_memIf 0 is in a set s of natural numbers and 1 is not, the mex of s is 1.
  • nat_mex_set_ne_of_memThe mex of a finite set s of natural numbers is not an element of s.
  • 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…
  • 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.
  • 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_parity_of_strategy_classLet T be a finite tree and S a class of positions of the Game of Arrows on T that contains the empty position, such that from every…

The proof, explained

The proof proceeds by strong induction on fuel. The core step establishes that from any position $p \in S$, no legal move can lead to an option with Grundy value equal to $e(p) \bmod 2$: if the move stays in $S$, the parity of $e$ alternates; if it leaves $S$, a legal reply move back into $S$ shows that $e(p) \bmod 2$ is already among the options from that neighbor, preventing the neighbor's Grundy value (the mex of its options) from equaling $e(p) \bmod 2$. A case split on $e(p) \bmod 2$ then shows the mex of the options from $p$ is 0 when $e(p)$ is even (as 0 is excluded) and 1 when $e(p)$ is odd (as 0 is reachable and 1 is excluded).

  1. We set up strong induction on `fuel` and express `fuel` as a successor $n + 1$.

    We proceed by strong induction on `fuel`. For any position $p \in S$ satisfying $e(p) < \text{fuel}$, the condition $0 \le e(p) < \text{fuel}$ implies $\text{fuel} \ge 1$. Hence, we can write $\text{fuel} = n + 1$ with $n = \text{fuel} - 1$, preparing to unfold the definition of the fuel-bounded Grundy value.

    lines 7–11

    uses Nat.strong_induction_on

      intro fuel
      induction fuel using Nat.strong_induction_on with
      | _ fuel ih =>
        intro p hp hlt
        obtain ⟨n, rfl⟩ : ∃ n, fuel = n + 1 := ⟨fuel - 1, by omega⟩
  2. No legal move from $p$ leads to a position whose Grundy value with fuel $n$ equals $e(p) \bmod 2$.

    Suppose for contradiction that some legal move $p \to q$ yields a position $q$ with Grundy value $e(p) \bmod 2$. The hypothesis `he` gives $e(q) = e(p) - 1$. By the closure hypothesis `hcl`, either $q \in S$ or there exists a reply move $q \to r$ with $r \in S$: - If $q \in S$, the induction hypothesis applies to $q$ with fuel $n$ (since $n < \text{fuel}$ and $e(q) < n$), showing its Grundy value is $e(q) \bmod 2$. But $e(p) \equiv e(q) + 1 \not\equiv e(q) \pmod 2$, a contradiction. - If there is a reply move $q \to r$ with $r \in S$, then $e(r) = e(q) - 1 = e(p) - 2$, so $e(r) \equiv e(p) \pmod 2$. Writing $n = n' + 1$, the induction hypothesis applied to $r$ with fuel $n'$ shows its Grundy value is $e(r) \bmod 2 = e(p) \bmod 2$. Thus, $e(p) \bmod 2$ is an option value from $q$. Since the Grundy value of $q$ with fuel $n = n' + 1$ is the mex of its options, it cannot equal any element in that finite set by `nat_mex_set_ne_of_mem` and `arrows_pos_grundy_options_finite`, contradicting our assumption.

    lines 12–24

    uses arrows_pos_grundy_options_finite, nat_mex_set_ne_of_mem

        have hnot : e p % 2 ∉ { m : ℕ | ∃ q, ArrowsLegalMove G p q ∧ m = arrows_pos_grundy G n q } := by
          rintro ⟨q, hq, hm⟩
          have heq := he p q hq
          rcases hcl p q hp hq with hS | ⟨r, hr, hSr⟩
          · rw [ih n (by omega) q hS (by omega)] at hm; omega
          · have her := he q r hr
            obtain ⟨n', rfl⟩ : ∃ n', n = n' + 1 := ⟨n - 1, by omega⟩
            have hrv : arrows_pos_grundy G n' r = e p % 2 := by
              rw [ih n' (by omega) r hSr (by omega)]; omega
            have hg : arrows_pos_grundy G (n' + 1) q = nat_mex_set
                { m : ℕ | ∃ q', ArrowsLegalMove G q q' ∧ m = arrows_pos_grundy G n' q' } := rfl
            exact nat_mex_set_ne_of_mem (arrows_pos_grundy_options_finite G n' q)
              ⟨r, hr, hrv.symm⟩ (hg ▸ hm.symm)
  3. If $e(p) \equiv 0 \pmod 2$, the Grundy value of $p$ with fuel $n + 1$ is $0$.

    By definition, the Grundy value with fuel $n + 1$ is the mex of the option values from $p$. Using `Nat.mod_two_eq_zero_or_one`, we split on the parity of $e(p)$. In the case $e(p) \equiv 0 \pmod 2$, the previous step showed that $0$ is not among the option values (`hnot`). By `nat_mex_set_eq_zero_of_not_mem`, the mex of any set of natural numbers not containing $0$ is $0$.

    lines 25–27

    uses Nat.mod_two_eq_zero_or_one, nat_mex_set_eq_zero_of_not_mem

        show nat_mex_set _ = _
        rcases Nat.mod_two_eq_zero_or_one (e p) with h0 | h1
        · rw [h0] at hnot ⊢; exact nat_mex_set_eq_zero_of_not_mem hnot
  4. If $e(p) \equiv 1 \pmod 2$, the Grundy value of $p$ with fuel $n + 1$ is $1$.

    When $e(p) \equiv 1 \pmod 2$, we have $e(p) \ge 1$. The existence hypothesis `hex` guarantees a legal move $p \to q$ with $q \in S$. Since $e(q) = e(p) - 1$, we have $e(q) \equiv 0 \pmod 2$, and by the induction hypothesis the Grundy value of $q$ with fuel $n$ is $0$. Thus $0$ is in the option set of $p$. Because $0$ is present and $1$ is excluded (by `hnot`), the mex of the option set is $1$ by `nat_mex_set_eq_one_of_mem`.

    lines 28–31

    uses nat_mex_set_eq_one_of_mem

        · rw [h1] at hnot ⊢
          obtain ⟨q, hq, hSq⟩ := hex p hp (by omega)
          have heq := he p q hq
          exact nat_mex_set_eq_one_of_mem ⟨q, hq, by rw [ih n (by omega) q hSq (by omega)]; omega⟩ hnot
Nat.strong_induction_on
Principle of strong induction on natural numbers: to prove a property holds for all $n$, it suffices to show it holds for $n$ assuming it holds for all $m < n$.
arrows_pos_grundy_options_finite
The set of Grundy values of all positions legally reachable in one move from a given position is finite.
nat_mex_set_ne_of_mem
The minimum excluded value (mex) of a finite set of natural numbers is not an element of that set.
Nat.mod_two_eq_zero_or_one
Every natural number modulo 2 is either 0 or 1.
nat_mex_set_eq_zero_of_not_mem
If 0 does not belong to a set of natural numbers, its minimum excluded value is 0.
nat_mex_set_eq_one_of_mem
If 0 belongs to a set of natural numbers and 1 does not, its minimum excluded value is 1.

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_eq_mod_two_of_class {V : Type*} [DecidableEq V] [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] (S : ArrowsPos V → Prop) (e : ArrowsPos V → ℕ)    (he : ∀ p q, ArrowsLegalMove G p q → e q + 1 = e p)    (hex : ∀ p, S p → 1 ≤ e p → ∃ q, ArrowsLegalMove G p q ∧ S q)    (hcl : ∀ p q, S p → ArrowsLegalMove G p q → S q ∨ ∃ r, ArrowsLegalMove G q r ∧ S r) :    ∀ fuel p, S p → e p < fuel → arrows_pos_grundy G fuel p = e p % 2 := by  intro fuel  induction fuel using Nat.strong_induction_on with  | _ fuel ih =>    intro p hp hlt    obtain ⟨n, rfl⟩ : ∃ n, fuel = n + 1 := ⟨fuel - 1, by omega⟩    have hnot : e p % 2 ∉ { m : ℕ | ∃ q, ArrowsLegalMove G p q ∧ m = arrows_pos_grundy G n q } := by      rintro ⟨q, hq, hm⟩      have heq := he p q hq      rcases hcl p q hp hq with hS | ⟨r, hr, hSr⟩      · rw [ih n (by omega) q hS (by omega)] at hm; omega      · have her := he q r hr        obtain ⟨n', rfl⟩ : ∃ n', n = n' + 1 := ⟨n - 1, by omega⟩        have hrv : arrows_pos_grundy G n' r = e p % 2 := by          rw [ih n' (by omega) r hSr (by omega)]; omega        have hg : arrows_pos_grundy G (n' + 1) q = nat_mex_set            { m : ℕ | ∃ q', ArrowsLegalMove G q q' ∧ m = arrows_pos_grundy G n' q' } := rfl        exact nat_mex_set_ne_of_mem (arrows_pos_grundy_options_finite G n' q)          ⟨r, hr, hrv.symm⟩ (hg ▸ hm.symm)    show nat_mex_set _ = _    rcases Nat.mod_two_eq_zero_or_one (e p) with h0 | h1    · rw [h0] at hnot ⊢; exact nat_mex_set_eq_zero_of_not_mem hnot    · rw [h1] at hnot ⊢      obtain ⟨q, hq, hSq⟩ := hex p hp (by omega)      have heq := he p q hq      exact nat_mex_set_eq_one_of_mem ⟨q, hq, by rw [ih n (by omega) q hSq (by omega)]; omega⟩ hnot
See it in the graphDiscuss this resultChallenge it