AFTD Auto-Formalizing Theoretical Domains

spider_two_leg_short_short_zero

theoremverified

At 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 outgoing.

Statement

theorem spider_two_leg_short_short_zero (fuel : ℕ) (hfuel : 3 ≤ fuel) :
    spider_gamma fuel CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = 0 ∧
      spider_gamma fuel CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = 0
Source
step towards spider_blocked_none_one_inward_one_outward
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • 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…
  • 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…
Used by 2

The proof, explained

The theorem establishes that a two-leg spider configuration with legs of length 1 (one inward, one outward) has Grundy value 0 for both incoming and outgoing centre statuses, provided the fuel is at least 3. The proof first checks that the fuel requirement $3 \le \text{fuel}$ matches the threshold needed for fuel independence, namely the sum of the leg lengths plus one ($1 + 1 + 1 = 3$). Applying `spider_gamma_fuel_independent` reduces each conjunct to evaluating the game value at the fixed fuel 3. Finally, since the state and fuel are completely concrete, both values are verified to be 0 by direct computation using `decide`.

  1. The available fuel is at least the sum of the leg lengths plus one. automation

    The sum of the lengths of the legs in `[(1, inward), (1, outward)]` plus 1 is $(1 + 1) + 1 = 3$. Since $\text{fuel} \ge 3$ by hypothesis `hfuel`, this inequality holds by simplification.

    lines 5–6

      have h : ((List.map Prod.fst [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)]).sum + 1) ≤ fuel := by
        simpa using hfuel
  2. It suffices to evaluate the game value separately for the incoming and outgoing centre statuses.

    The goal is a conjunction of two claims, one for `CentreStatus.incoming` and one for `CentreStatus.outgoing`. Applying `constructor` splits the goal into these two independent cases.

    line 7

      constructor
  3. The game value is 0 when the centre status is incoming. automation

    Using the fuel bound $h$, rewriting with `spider_gamma_fuel_independent` reduces the evaluation from arbitrary `fuel` to the minimal fuel bound $3 = (1 + 1) + 1$. Because all parameters are concrete, `decide` evaluates the finite game tree and verifies that the resulting mex is 0.

    lines 8–9

    uses spider_gamma_fuel_independent

      · rw [spider_gamma_fuel_independent fuel _ _ h]
        decide
  4. The game value is 0 when the centre status is outgoing. automation

    Similarly, `spider_gamma_fuel_independent` reduces the evaluation at `fuel` to the evaluation at fuel 3, which is then computed to be 0 by `decide`.

    lines 10–11

    uses spider_gamma_fuel_independent

      · rw [spider_gamma_fuel_independent fuel _ _ h]
        decide
spider_gamma_fuel_independent
For any centre status `s` and leg list `L`, if `fuel` is at least the sum of the leg lengths plus 1, then `spider_gamma fuel s L` is independent of additional fuel and equals `spider_gamma ((L.map Prod.fst).sum + 1) s L`.

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

/-- The two-short-leg sub-state reached by a j = 1 cut of the long leg has value 0 at either centre status. -/theorem spider_two_leg_short_short_zero (fuel : ℕ) (hfuel : 3 ≤ fuel) :    spider_gamma fuel CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = 0 ∧      spider_gamma fuel CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = 0 := by  have h : ((List.map Prod.fst [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)]).sum + 1) ≤ fuel := by    simpa using hfuel  constructor  · rw [spider_gamma_fuel_independent fuel _ _ h]    decide  · rw [spider_gamma_fuel_independent fuel _ _ h]    decide
See it in the graphDiscuss this resultChallenge it