spider_blocked_none_one_inward_one_outward
For the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
Statement
theorem spider_blocked_none_one_inward_one_outward (r : ℕ) (hr : 1 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
spider_gamma (r + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)] = r- Source
- step towards spider_eventual_parity_two_three
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 18
- 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_gamma_reversalFor every fuel, centre status s and leg list L, the value of the spider state (s;L) equals the value of the state obtained by exchanging…
- spider_blocked_incoming_one_outwardFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
- spider_none_one_inward_one_outward_optsThe explicit closed-form option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after substituting the sub-state values: the two…
- 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_two_leg_short_short_zeroAt any fuel at least 3, the two-leg state with centre incoming and legs (1,inward),(1,outward) has value 0, and likewise with centre…
- 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 φ.
- spider_blocked_none_one_inward_one_outward_baseThe base case r = 1 of the κ₁ blocked family: for both far ends φ ≠ free, (none;{1^in,1^out,(1,φ)}) at canonical fuel 4 has value 1.
- spider_none_one_inward_one_outward_raw_optsThe raw option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after one unfolding step, in the exact order the recursion…
- spider_blocked_none_one_inward_one_outward_raw_opts_eqFor r ≥ 2 and φ ≠ free, the value of (none;{(1,inward),(1,outward),(r,φ)}) at fuel r+3 is the mex of the raw option list…
- spider_none_one_inward_one_outward_opts_not_memFor r ≥ 2 and φ ≠ free, the level r is not a member of the closed-form option list of the κ₁ family.
- spider_none_one_inward_one_outward_opts_all_lt_memFor r ≥ 2 and φ ≠ free, every k < r is a member of the closed-form option list of the κ₁ family.
- 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_none_one_inward_one_outward_opts_mexFor r ≥ 2 and φ ≠ free, the mex of the explicit option list of the κ₁ configuration equals r.
- 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_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
The proof, explained
The theorem is proved by strong induction on the leg length r ≥ 1, generalizing over the non-free leg end φ. When r < 2, the assumption 1 ≤ r forces r = 1, which is solved by the base-case lemma spider_blocked_none_one_inward_one_outward_base. For r ≥ 2, the game value is expressed as the mex of raw move options, which simplifies via the induction hypothesis on legs of length r' < r to an options list whose mex evaluates directly to r.
It suffices to prove the theorem for r assuming it holds for all strictly smaller leg lengths m < r and all non-free endpoints φ.
We proceed by strong induction on r using Nat.strong_induction_on, generalizing over the endpoint φ so that the induction hypothesis applies to any non-free endpoint at smaller leg lengths.
uses
Nat.strong_induction_oninduction' r using Nat.strong_induction_on with r ih generalizing φWe split the proof into two cases: r ≥ 2 and r < 2.
By le_or_gt applied to 2 and r, either 2 ≤ r or r < 2. The inductive reduction requires leg length at least 2, while r < 2 isolates the base case.
uses
le_or_gtrcases le_or_gt 2 r with hr2 | hr2
For r ≥ 2, the game value γ(r + 3, none, [(1, inward), (1, outward), (r, φ)]) equals r.
We rewrite the game value as the mex of raw options via spider_blocked_none_one_inward_one_outward_raw_opts_eq. By spider_blocked_none_one_inward_one_outward_opts_eq, this raw mex equals the mex of the simplified options list, provided the induction hypothesis holds for all r' < r (which we supply from ih). Finally, spider_none_one_inward_one_outward_opts_mex evaluates this mex to r.
uses
spider_blocked_none_one_inward_one_outward_raw_opts_eq,spider_blocked_none_one_inward_one_outward_opts_eq,spider_none_one_inward_one_outward_opts_mex· rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq r hr2 φ hφ] rw [spider_blocked_none_one_inward_one_outward_opts_eq r hr2 φ hφ] · exact spider_none_one_inward_one_outward_opts_mex r hr2 φ hφ · intro r' hr' hr'1 φ' hφ' exact ih r' hr' hr'1 φ' hφ'
For r < 2, the game value γ(r + 3, none, [(1, inward), (1, outward), (r, φ)]) equals r.
From the hypotheses 1 ≤ r and r < 2, linear integer arithmetic determines that r = 1. Substituting r = 1 reduces the goal to γ(4, none, [(1, inward), (1, outward), (1, φ)]) = 1, which holds by the base-case lemma spider_blocked_none_one_inward_one_outward_base.
uses
spider_blocked_none_one_inward_one_outward_base· have hr1 : r = 1 := by omega subst hr1 exact spider_blocked_none_one_inward_one_outward_base φ hφ
Nat.strong_induction_on- Principle of strong induction on natural numbers: to prove a property holds for all n, it suffices to prove it for n assuming it holds for all m < n.
le_or_gt- In any linearly ordered type, for any two elements a and b, either a ≤ b or b < a.
spider_blocked_none_one_inward_one_outward_raw_opts_eq- For r ≥ 2 and φ ≠ free, the game value of the configuration is the minimal excluded value (mex) of its raw move options.
spider_blocked_none_one_inward_one_outward_opts_eq- Assuming the theorem holds for all leg lengths r' < r, the mex of the raw options equals the mex of the simplified options list.
spider_none_one_inward_one_outward_opts_mex- For r ≥ 2 and φ ≠ free, the minimal excluded value (mex) of the simplified options list evaluates to r.
spider_blocked_none_one_inward_one_outward_base- Base case r = 1: the game value γ(4, none, [(1, inward), (1, outward), (1, φ)]) equals 1 for any non-free leg end φ.
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 (n;{1^in,1^out}) (the paper's κ₁): the value at level r is r, for both far ends. -/theorem spider_blocked_none_one_inward_one_outward (r : ℕ) (hr : 1 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : spider_gamma (r + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)] = r := by induction' r using Nat.strong_induction_on with r ih generalizing φ rcases le_or_gt 2 r with hr2 | hr2 · rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq r hr2 φ hφ] rw [spider_blocked_none_one_inward_one_outward_opts_eq r hr2 φ hφ] · exact spider_none_one_inward_one_outward_opts_mex r hr2 φ hφ · intro r' hr' hr'1 φ' hφ' exact ih r' hr' hr'1 φ' hφ' · have hr1 : r = 1 := by omega subst hr1 exact spider_blocked_none_one_inward_one_outward_base φ hφ