spider_blocked_incoming_one_outward
For the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
Statement
theorem spider_blocked_incoming_one_outward (r : ℕ) (hr : 1 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)] = r ^^^ 1- Source
- step towards spider_eventual_parity_two_three
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- spider_gamma_fuel_independentFor every fuel at least the total number of markable edges in L plus one, the value of spider_gamma does not depend on the fuel: it equals…
- spider_blocked_incoming_one_outward_oneFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(1) equals 1 ^^^ 1 for both φ ≠ free.
- 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…
- spider_mex_incoming_one_outwardThe minimum excluded value of the explicit options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2…
- 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.
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- 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_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 3
- spider_blocked_none_one_inward_one_outward_opts_eqFor r ≥ 2, φ ≠ free, and assuming the closed form for all smaller levels, the mex of the raw option list equals the mex of the explicit…
- spider_blocked_none_one_inward_one_outwardFor the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
- spider_blocked_outgoing_one_inwardFor the mirror configuration (out;{(1,inward)}), the blocked family at level r equals r xor 1 for every r ≥ 1 and both far ends φ.
The proof, explained
The identity is proved by strong induction on the leg length r ≥ 1. The base case r = 1 is established by a dedicated lemma. For r ≥ 2, the recursive definition of the Grundy value γ is unfolded into the mex of all reachable options; the induction hypothesis simplifies this list of options to an explicit sequence of values, whose mex is then shown to equal r ⊕ 1.
It suffices to prove the identity for r assuming it holds for all smaller leg lengths m < r with 1 ≤ m.
We revert the hypotheses hr, φ, and hφ and set up strong induction on r using Nat.strong_induction_on. We then reintroduce the hypotheses, obtaining the induction hypothesis ih for all 1 ≤ m < r.
uses
Nat.strong_induction_onrevert hr φ hφ induction r using Nat.strong_induction_on with | h r ih => intro hr φ hφ
The argument splits into the base case r = 1 and the strictly greater case r > 1.
From the assumption 1 ≤ r, eq_or_lt_of_le yields either r = 1 or 1 < r (meaning r ≥ 2).
uses
eq_or_lt_of_lercases eq_or_lt_of_le hr with rfl | hr2
The identity holds in the base case r = 1.
When r = 1, the goal is γ(3, incoming, [(1, outward), (1, φ)]) = 1 ⊕ 1, which holds directly by the precomputed base-case lemma spider_blocked_incoming_one_outward_one.
uses
spider_blocked_incoming_one_outward_one· exact spider_blocked_incoming_one_outward_one φ hφFor r > 1, the game value γ is expressed as the mex of reachable option values.
We unfold the definition of spider_gamma using spider_gamma.eq_def and simplify the pattern matches. Since the configuration has multiple legs and incoming center status, the value reduces to the mex (nat_mex_list) of all legally reachable subgame values.
uses
spider_gamma.eq_def· rw [spider_gamma.eq_def] dsimp only
The list of option values simplifies to an explicit list via the induction hypothesis.
We rewrite the options list using spider_blocked_incoming_one_outward_options_eq, providing the induction hypothesis ih to evaluate the values of smaller subgames. This simplifies the options to an explicit concatenation of single-move values and pairs of moves.
uses
spider_blocked_incoming_one_outward_options_eqrw [spider_blocked_incoming_one_outward_options_eq r hr2 φ hφ (fun r' hr' hr'1 φ' hφ' => ih r' hr' hr'1 φ' hφ')]
The mex of the options list is r ⊕ 1, completing the induction.
Applying spider_mex_incoming_one_outward directly computes the minimum excluded value of the explicit options list, proving it equals r ⊕ 1.
uses
spider_mex_incoming_one_outwardexact spider_mex_incoming_one_outward r hr2 φ hφ
Nat.strong_induction_on- Strong induction principle for natural numbers: to prove a property for all n, it suffices to prove it for n assuming it holds for all m < n.
eq_or_lt_of_le- In a partial order, a ≤ b implies a = b or a < b.
spider_blocked_incoming_one_outward_one- The base case r = 1: the Grundy value γ with fuel 3, incoming center, and legs [(1, outward), (1, φ)] equals 1 ⊕ 1 for any non-free boundary condition φ.
spider_gamma.eq_def- The defining recursive equation for spider_gamma, expressing the value for non-zero fuel and multiple legs as the mex of legal move values.
spider_blocked_incoming_one_outward_options_eq- For r ≥ 2, simplifies the list of legal options from [(1, outward), (r, φ)] with incoming center into an explicit concatenated list of values, using the induction hypothesis for smaller subgames.
spider_mex_incoming_one_outward- For r ≥ 2 and non-free φ, the mex of the explicit list of reachable option values equals r ⊕ 1.
- The detailed case analysis enumerating the legal moves and the algebraic calculation of their minimum excluded value (mex) are factored out into the helper lemmas `spider_blocked_incoming_one_outward_options_eq` and `spider_mex_incoming_one_outward`.
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.
/-- Blocked family of the configuration (i;{1^outward}) (the paper's κ₂): the value at level r is r xor 1, for both far ends. -/theorem spider_blocked_incoming_one_outward (r : ℕ) (hr : 1 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)] = r ^^^ 1 := by revert hr φ hφ induction r using Nat.strong_induction_on with | h r ih => intro hr φ hφ rcases eq_or_lt_of_le hr with rfl | hr2 · exact spider_blocked_incoming_one_outward_one φ hφ · rw [spider_gamma.eq_def] dsimp only rw [spider_blocked_incoming_one_outward_options_eq r hr2 φ hφ (fun r' hr' hr'1 φ' hφ' => ih r' hr' hr'1 φ' hφ')] exact spider_mex_incoming_one_outward r hr2 φ hφ