AFTD Auto-Formalizing Theoretical Domains

spider_blocked_incoming_one_outward_one

theoremverified

For the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(1) equals 1 ^^^ 1 for both φ ≠ free.

Statement

theorem spider_blocked_incoming_one_outward_one (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    spider_gamma 3 CentreStatus.incoming [(1, SpiderLegEnd.outward), (1, φ)] = 1 ^^^ 1
Source
step towards spider_blocked_incoming_one_outward
Verified
19 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • 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 1

The proof, explained

The theorem evaluates the Sprague-Grundy function `spider_gamma` for a two-legged spider graph configuration with incoming centre status and leg parameters (1, outward) and (1, φ), showing it equals the nim-sum 1 ^^^ 1. A case analysis on the leg-end status φ yields three possibilities. The case φ = free is eliminated immediately as it contradicts the hypothesis φ ≠ free, while the remaining cases φ = inward and φ = outward are closed terms verified by direct computational evaluation.

  1. It suffices to verify the equality for each of the three possible values of φ: free, inward, and outward.

    The leg-end status type `SpiderLegEnd` is an inductive type with three constructors (`free`, `inward`, and `outward`). We split the proof into these three cases.

    line 4

      rcases φ with _ | _ | _
  2. The case φ = free is ruled out by contradiction.

    When φ is `free`, the assumption hφ asserts that `free ≠ free`. Since equality is reflexive (`rfl`), this is an immediate contradiction (`absurd`).

    line 5

    uses absurd, rfl

      · exact absurd rfl hφ
  3. The identity holds when φ = inward. automation

    When φ is `inward`, both sides of the equation are closed terms with no free variables. The `decide` tactic computes the Sprague-Grundy value `spider_gamma` on the configuration (incoming; [(1, outward), (1, inward)]) and confirms that it equals the nim-sum 1 ^^^ 1 = 0.

    line 6

      · decide
  4. The identity holds when φ = outward. automation

    Similarly, when φ is `outward`, the configuration contains only concrete parameters. The `decide` tactic computes `spider_gamma` on (incoming; [(1, outward), (1, outward)]) and verifies that it evaluates to 1 ^^^ 1 = 0.

    line 7

      · decide
absurd
From a proposition A and its negation ¬A, any conclusion B follows (principle of explosion).
rfl
Equality is reflexive: for every term a, a = a.

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 base case r = 1 for the configuration κ₂ = (in;{(1,outward)}) evaluates to 1 ^^^ 1. -/theorem spider_blocked_incoming_one_outward_one (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    spider_gamma 3 CentreStatus.incoming [(1, SpiderLegEnd.outward), (1, φ)] = 1 ^^^ 1 := by  rcases φ with _ | _ | _  · exact absurd rfl hφ  · decide  · decide
See it in the graphDiscuss this resultChallenge it