AFTD Auto-Formalizing Theoretical Domains

spider_blocked_none_one_inward_one_outward_base

theoremverified

The 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.

Statement

theorem spider_blocked_none_one_inward_one_outward_base (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    spider_gamma 4 CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (1, φ)] = 1
Source
step towards spider_blocked_none_one_inward_one_outward
Verified
20 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
  • 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…
Used by 1

The proof, explained

The proof proceeds by case analysis on the leg end φ. The case φ = free is ruled out immediately by the hypothesis that φ ≠ free. In the remaining cases, φ = inward and φ = outward, all arguments to the recursive function `spider_gamma` are concrete, and both equalities evaluate to 1 by definitional equality (reflexivity).

  1. The case φ = free is eliminated, leaving only φ = inward and φ = outward.

    We perform a case analysis on the inductive type `SpiderLegEnd` for the leg end φ. When φ is `SpiderLegEnd.free`, the hypothesis `hφ : φ ≠ SpiderLegEnd.free` becomes `SpiderLegEnd.free ≠ SpiderLegEnd.free`, which is a contradiction.

    lines 4–5

      cases φ
      · contradiction
  2. When φ = inward, the game value is 1.

    Substituting φ = inward leaves a fully concrete game state with centre status `none` and three legs of length 1 (two inward, one outward). Expanding the recursive definition of `spider_gamma` with fuel 4 computes the Sprague-Grundy value to be 1, so the goal holds by definitional equality.

    line 6

      · rfl
  3. When φ = outward, the game value is 1.

    Similarly, substituting φ = outward yields a fully concrete game state with one inward leg and two outward legs of length 1. Unfolding `spider_gamma` with fuel 4 again evaluates definitionally to 1.

    line 7

      · rfl

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

/-- Base case r = 1 of the κ₁ blocked family. -/theorem spider_blocked_none_one_inward_one_outward_base (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    spider_gamma 4 CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (1, φ)] = 1 := by  cases φ  · contradiction  · rfl  · rfl
See it in the graphDiscuss this resultChallenge it