AFTD Auto-Formalizing Theoretical Domains

spider_mex_two_leg_one_free

theoremverified

Given an explicit options list where every element has parity k % 2, the minimum excluded value is 1 - k % 2 (which is 1 when k is even, since 0 is in the list and all elements are even; and 0 when k is odd, since all elements are odd).

Statement

theorem spider_mex_two_leg_one_free (k : ℕ) (hk : 1 ≤ k)
    (h_parity : ∀ (idx : ℕ) (delta : SpiderLegEnd), idx < k - 1 →
      delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward →
      spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)] % 2 = (idx + 2) % 2) :
    nat_mex_list
      ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++
       (List.range (k - 1)).flatMap (fun idx =>
         let j := idx + 2
         let d := k - j
         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>
           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]
         )
       )) = 1 - k % 2
Source
step towards spider_two_leg_one_free
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • nat_xor_mod_twoFor any natural numbers a and b, (a ^^^ b) % 2 = (a + b) % 2.
  • nat_mex_list_eq_oneIf a list of naturals contains 0 but not 1, then its mex is 1.
  • SpiderLegEndThe end condition of an attached leg in a spider state is either free (no arc on the leg), inward (pointing towards the centre), or…
  • nat_mex_list_eq_zeroIf a list of naturals does not contain 0, then its mex (minimum excluded value) is 0.
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
  • CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
  • spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…

The proof, explained

The minimum excluded value (mex) of the options list is determined by the parity of its elements. The helper lemma spider_mex_two_leg_one_free_parity first proves that every option in the list has parity k % 2, by checking the explicit prefix elements directly and applying the inductive parity hypothesis to the recursive subgame options. A case split on the parity of k then determines the mex: if k is even, 0 is present and 1 is absent, so the mex is 1 = 1 - k % 2; if k is odd, all elements are odd so 0 is absent, and the mex is 0 = 1 - k % 2.

  1. Every option from the explicit prefix list [k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] has parity equal to k % 2.

    We unfold membership in the options list into a disjunction using List.mem_append, List.mem_cons, List.not_mem_nil, or_false, List.mem_flatMap, List.mem_range, and List.mem_map, then split into cases. If x = k, the parities match by reflexivity. If x = k % 2, idempotence of modulo (Nat.mod_mod) gives (k % 2) % 2 = k % 2. If x = (k - 1) ^^^ 1, nat_xor_mod_two reduces the parity to ((k - 1) + 1) % 2, which equals k % 2 by linear arithmetic (omega) since 1 ≤ k.

    lines 15–23

    uses List.mem_append, List.mem_cons, List.not_mem_nil, or_false, List.mem_flatMap, List.mem_range, List.mem_map, Nat.mod_mod, nat_xor_mod_two

      simp only [List.mem_append, List.mem_cons, List.not_mem_nil, or_false,
                 List.mem_flatMap, List.mem_range, List.mem_map] at hx
      rcases hx with (rfl | rfl | rfl | rfl) | ⟨idx, hidx, delta, hdelta, rfl⟩
      · rfl
      · rw [Nat.mod_mod]
      · rw [nat_xor_mod_two]
        omega
      · rw [nat_xor_mod_two]
        omega
  2. Every option produced by recursive subgames in the flatMap also has parity k % 2, completing the proof of spider_mex_two_leg_one_free_parity.

    Any option from the flatMap is of the form d ^^^ γ where d = k - (idx + 2), idx < k - 1, and γ is the Grundy value of the subgame for a leg end δ ∈ {inward, outward}. Using nat_xor_mod_two, its parity is (d + γ) % 2. By the induction hypothesis h_parity, γ % 2 = (idx + 2) % 2 in both cases (via Or.inl for inward and Or.inr for outward). Substituting this, the sum (k - (idx + 2)) + (idx + 2) simplifies to k because idx + 2 ≤ k, so linear arithmetic (omega) finishes the equality with k % 2.

    lines 24–29

    uses nat_xor_mod_two, Or.inl, Or.inr

      · rw [nat_xor_mod_two]
        rcases hdelta with (rfl | rfl)
        · have hp := h_parity idx SpiderLegEnd.inward hidx (Or.inl rfl)
          omega
        · have hp := h_parity idx SpiderLegEnd.outward hidx (Or.inr rfl)
          omega
  3. Every element in the options list for spider_mex_two_leg_one_free has parity equal to k % 2.

    We introduce an arbitrary element x and its membership hypothesis, then apply the lemma spider_mex_two_leg_one_free_parity to conclude x % 2 = k % 2 for all options in the list.

    lines 45–54

    uses spider_mex_two_leg_one_free_parity

      have h_all : ∀ x ∈ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++
           (List.range (k - 1)).flatMap (fun idx =>
             let j := idx + 2
             let d := k - j
             [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>
               d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]
             )
           )), x % 2 = k % 2 := by
        intro x hx
        exact spider_mex_two_leg_one_free_parity k hk h_parity x hx
  4. It suffices to consider the cases where k is even (k % 2 = 0) and where k is odd (k % 2 = 1).

    By Nat.mod_two_eq_zero_or_one, k % 2 is either 0 or 1. We perform a case split on this disjunction.

    line 55

    uses Nat.mod_two_eq_zero_or_one

      rcases Nat.mod_two_eq_zero_or_one k with hk0 | hk1
  5. When k is even (k % 2 = 0), the minimum excluded value of the options list is 1, which equals 1 - k % 2.

    Since k % 2 = 0, the second element of the explicit list is 0, so 0 is in the list by List.mem_append and List.mem_cons. Conversely, 1 cannot be in the list: if it were, the parity theorem h_all would force 1 % 2 = k % 2 = 0, an arithmetic contradiction. Because 0 is in the list and 1 is not, nat_mex_list_eq_one shows the mex is 1, and omega confirms 1 = 1 - k % 2.

    lines 56–80

    uses List.mem_append, List.mem_cons, nat_mex_list_eq_one

      · have h0 : 0 ∈ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++
           (List.range (k - 1)).flatMap (fun idx =>
             let j := idx + 2
             let d := k - j
             [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>
               d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]
             )
           )) := by
          simp only [List.mem_append, List.mem_cons]
          left; right; left
          exact hk0.symm
        have h1 : 1 ∉ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++
           (List.range (k - 1)).flatMap (fun idx =>
             let j := idx + 2
             let d := k - j
             [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>
               d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]
             )
           )) := by
          intro h1_in
          have := h_all 1 h1_in
          rw [hk0] at this
          omega
        rw [nat_mex_list_eq_one _ h0 h1]
        omega
  6. When k is odd (k % 2 = 1), the minimum excluded value of the options list is 0, which equals 1 - k % 2.

    When k % 2 = 1, all elements in the list have odd parity by h_all. In particular, 0 cannot be in the list because 0 % 2 = 0 ≠ 1. Because 0 is not in the list, nat_mex_list_eq_zero implies that the mex is 0, and omega confirms 0 = 1 - k % 2.

    lines 81–94

    uses nat_mex_list_eq_zero

      · have h0 : 0 ∉ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++
           (List.range (k - 1)).flatMap (fun idx =>
             let j := idx + 2
             let d := k - j
             [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>
               d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]
             )
           )) := by
          intro h0_in
          have := h_all 0 h0_in
          rw [hk1] at this
          omega
        rw [nat_mex_list_eq_zero _ h0]
        omega
List.mem_append
An element belongs to the concatenation of two lists if and only if it belongs to the first list or the second list.
List.mem_cons
An element belongs to a cons-list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil
No element belongs to the empty list.
or_false
For any proposition p, p ∨ False is equivalent to p.
List.mem_flatMap
An element b belongs to the flat-mapping of f over l if and only if there exists some a in l such that b belongs to f a.
List.mem_range
A natural number m belongs to List.range n if and only if m < n.
List.mem_map
An element b belongs to the image List.map f l if and only if b = f a for some a in l.
Nat.mod_mod
Modulo is idempotent: (a % n) % n = a % n for any natural numbers a and n.
nat_xor_mod_two
The parity of a bitwise XOR equals the parity of the sum: (a ^^^ b) % 2 = (a + b) % 2.
Or.inl
Constructs a proof of a disjunction a ∨ b from a proof of the left disjunct a.
Or.inr
Constructs a proof of a disjunction a ∨ b from a proof of the right disjunct b.
spider_mex_two_leg_one_free_parity
Every option in the two-free-leg options list has parity equal to k % 2, given the parity induction hypothesis for recursive subgames.
Nat.mod_two_eq_zero_or_one
Every natural number n is either even (n % 2 = 0) or odd (n % 2 = 1).
nat_mex_list_eq_one
If 0 belongs to a list of natural numbers and 1 does not, the minimum excluded value (mex) of the list is 1.
nat_mex_list_eq_zero
If 0 does not belong to a list of natural numbers, the minimum excluded value (mex) of the list is 0.

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 spider_mex_two_leg_one_free_parity (k : ℕ) (hk : 1 ≤ k)    (h_parity : ∀ (idx : ℕ) (delta : SpiderLegEnd), idx < k - 1 →      delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward →      spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)] % 2 = (idx + 2) % 2)    (x : ℕ)    (hx : x ∈ [k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++       (List.range (k - 1)).flatMap (fun idx =>         let j := idx + 2         let d := k - j         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]         )       )) :    x % 2 = k % 2 := by  simp only [List.mem_append, List.mem_cons, List.not_mem_nil, or_false,             List.mem_flatMap, List.mem_range, List.mem_map] at hx  rcases hx with (rfl | rfl | rfl | rfl) | ⟨idx, hidx, delta, hdelta, rfl⟩  · rfl  · rw [Nat.mod_mod]  · rw [nat_xor_mod_two]    omega  · rw [nat_xor_mod_two]    omega  · rw [nat_xor_mod_two]    rcases hdelta with (rfl | rfl)    · have hp := h_parity idx SpiderLegEnd.inward hidx (Or.inl rfl)      omega    · have hp := h_parity idx SpiderLegEnd.outward hidx (Or.inr rfl)      omega/-- The mex of the options list for two free legs 1 and k equals 1 - k % 2, assuming each subgame option has parity (idx + 2) % 2. -/theorem spider_mex_two_leg_one_free (k : ℕ) (hk : 1 ≤ k)    (h_parity : ∀ (idx : ℕ) (delta : SpiderLegEnd), idx < k - 1 →      delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward →      spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)] % 2 = (idx + 2) % 2) :    nat_mex_list      ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++       (List.range (k - 1)).flatMap (fun idx =>         let j := idx + 2         let d := k - j         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]         )       )) = 1 - k % 2 := by  have h_all : ∀ x ∈ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++       (List.range (k - 1)).flatMap (fun idx =>         let j := idx + 2         let d := k - j         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]         )       )), x % 2 = k % 2 := by    intro x hx    exact spider_mex_two_leg_one_free_parity k hk h_parity x hx  rcases Nat.mod_two_eq_zero_or_one k with hk0 | hk1  · have h0 : 0 ∈ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++       (List.range (k - 1)).flatMap (fun idx =>         let j := idx + 2         let d := k - j         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]         )       )) := by      simp only [List.mem_append, List.mem_cons]      left; right; left      exact hk0.symm    have h1 : 1 ∉ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++       (List.range (k - 1)).flatMap (fun idx =>         let j := idx + 2         let d := k - j         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]         )       )) := by      intro h1_in      have := h_all 1 h1_in      rw [hk0] at this      omega    rw [nat_mex_list_eq_one _ h0 h1]    omega  · have h0 : 0 ∉ ([k, k % 2, (k - 1) ^^^ 1, (k - 1) ^^^ 1] ++       (List.range (k - 1)).flatMap (fun idx =>         let j := idx + 2         let d := k - j         [SpiderLegEnd.inward, SpiderLegEnd.outward].map (fun delta =>           d ^^^ spider_gamma (k + 1) CentreStatus.incoming [(idx + 1, delta), (1, SpiderLegEnd.free)]         )       )) := by      intro h0_in      have := h_all 0 h0_in      rw [hk1] at this      omega    rw [nat_mex_list_eq_zero _ h0]    omega
See it in the graphDiscuss this resultChallenge it