spider_gamma_swap_two
The Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.
Statement
theorem spider_gamma_swap_two (fuel : ℕ) (s : CentreStatus) (A B : ℕ × SpiderLegEnd) :
spider_gamma fuel s [A, B] = spider_gamma fuel s [B, A]- Source
- step towards spider_blocked_incoming_one_inward
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- nat_mex_list_append_commFor any two lists of natural numbers l1 and l2, nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- 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…
- spider_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- spider_rhoThe function spider_rho takes h : ℕ and delta, phi : SpiderLegEnd, returning h if phi = free; if phi = inward, it returns h % 2 when delta…
- Used by 2
- spider_gamma_rotate_three_short_legsFor any leg p, centre status and fuel, the value of (s;{p,1^in,1^out}) equals the value of (s;{1^in,1^out,p}): the leg p may be moved from…
- spider_blocked_incoming_one_outward_options_eqFor r ≥ 2, the raw options list generated by [(1, outward), (r, φ)] at fuel r + 2 with centre status incoming unfolds to the explicit list…
The proof, explained
The Grundy value of a two-legged spider state is shown to be symmetric in the two legs by case analysis on the recursion fuel and the centre status. When the centre is free, the Grundy value is the XOR sum of the two legs' individual values, which is symmetric by the commutativity of bitwise XOR. When the centre is not free, the Grundy value is the mex of all moves available from either leg; swapping the legs simply swaps the two blocks of moves in the concatenated options list, leaving the overall mex unchanged.
The Grundy value is invariant under swapping the two legs when fuel = 0.
When the recursion fuel is 0, `spider_gamma` evaluates to 0 by definition regardless of the list of legs, so both sides are definitionally equal to 0 and the goal is solved by reflexivity (`rfl`).
cases fuel with | zero => rfl
When fuel = f + 1 and the centre status is free, swapping the two legs does not change the Grundy value.
For a free centre, `spider_gamma` computes the XOR sum of `spider_rho_star` over the leg list, initialized with 0. Simplifying both sides gives 0 ^^^ ρ*(A) ^^^ ρ*(B) on the left and 0 ^^^ ρ*(B) ^^^ ρ*(A) on the right. Removing the leading zero with `Nat.zero_xor` reduces this to ρ*(A) ^^^ ρ*(B) = ρ*(B) ^^^ ρ*(A), which holds by commutativity of XOR (`Nat.xor_comm`).
uses
Nat.zero_xor,Nat.xor_comm| succ f => cases s with | free => dsimp [spider_gamma] rw [Nat.zero_xor, Nat.zero_xor, Nat.xor_comm]When fuel = f + 1 and the centre status is not free, swapping the two legs does not change the Grundy value.
When the centre status is not free (covering `none`, `incoming`, and `outgoing`), `spider_gamma` computes the mex (`nat_mex_list`) of the combined moves available from each leg. Expanding the flat-map over the list of legs and evaluating index erasure splits the options for [A, B] into the moves on A concatenated with the moves on B, whereas for [B, A] they appear as moves on B concatenated with moves on A. Commuting the two sublists under `nat_mex_list` via `nat_mex_list_append_comm` establishes equality.
uses
List.flatMap_cons,List.flatMap_nil,List.append_nil,nat_mex_list_append_comm| _ => dsimp [spider_gamma] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil] dsimp [List.eraseIdx] rw [nat_mex_list_append_comm]
Nat.zero_xor- Bitwise exclusive-or of zero with any natural number x yields x (0 ^^^ x = x).
Nat.xor_comm- Bitwise exclusive-or on natural numbers is commutative (x ^^^ y = y ^^^ x).
List.flatMap_cons- Flat-mapping a function over a non-empty list x :: xs equals the result of the function on x concatenated with the flat-map over the tail xs.
List.flatMap_nil- Flat-mapping any function over the empty list yields the empty list.
List.append_nil- Appending the empty list to any list leaves the list unchanged (as ++ [] = as).
nat_mex_list_append_comm- The minimum excluded value (mex) of the concatenation of two lists of natural numbers is independent of the concatenation order: mex(l1 ++ l2) = mex(l2 ++ l1).
- The `fuel` parameter is an explicit recursion bound required for Lean's termination checker when defining `spider_gamma`; it has no game-theoretic meaning beyond ensuring termination.
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.
/-- The Grundy value of a two-legged spider state is invariant under swapping the two legs in the list. -/theorem spider_gamma_swap_two (fuel : ℕ) (s : CentreStatus) (A B : ℕ × SpiderLegEnd) : spider_gamma fuel s [A, B] = spider_gamma fuel s [B, A] := by cases fuel with | zero => rfl | succ f => cases s with | free => dsimp [spider_gamma] rw [Nat.zero_xor, Nat.zero_xor, Nat.xor_comm] | _ => dsimp [spider_gamma] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil] dsimp [List.eraseIdx] rw [nat_mex_list_append_comm]