AFTD Auto-Formalizing Theoretical Domains

spider_blocked_incoming_one_outward

theoremverified

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

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.

  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.

    lines 4–7

    uses Nat.strong_induction_on

      revert hr φ hφ
      induction r using Nat.strong_induction_on with
      | h r ih =>
        intro hr φ hφ
  2. 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).

    line 8

    uses eq_or_lt_of_le

        rcases eq_or_lt_of_le hr with rfl | hr2
  3. 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.

    line 9

    uses spider_blocked_incoming_one_outward_one

        · exact spider_blocked_incoming_one_outward_one φ hφ
  4. 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.

    lines 10–11

    uses spider_gamma.eq_def

        · rw [spider_gamma.eq_def]
          dsimp only
  5. 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.

    line 12

    uses spider_blocked_incoming_one_outward_options_eq

          rw [spider_blocked_incoming_one_outward_options_eq r hr2 φ hφ (fun r' hr' hr'1 φ' hφ' => ih r' hr' hr'1 φ' hφ')]
  6. 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.

    line 13

    uses spider_mex_incoming_one_outward

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

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

/-- 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φ
See it in the graphDiscuss this resultChallenge it