spider_mex_two_leg_one_free
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.
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.
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_twosimp 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
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.
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
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.
uses
spider_mex_two_leg_one_free_parityhave 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
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.
uses
Nat.mod_two_eq_zero_or_onercases Nat.mod_two_eq_zero_or_one k with hk0 | hk1
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.
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
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.
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.
- The options list is constructed using bitwise operations and subgame transitions from the spider game; the proof relies on linear integer arithmetic modulo 2 (`omega`) to verify the index and parity relations.
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 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