AFTD Auto-Formalizing Theoretical Domains

spider_blocked_two_three_level_five_options

theoremverified

One unfolding step of the recursion for the level-5 root state (none;{(5,inward),2^*,3^*}) at fuel n+1: the value is the mex of the list of the 19 options the recursion generates, where each option is a coefficient d (written as a numeral) xor spider_gamma at fuel n of the corresponding reduced position, in the exact order in which the recursion enumerates the legs, the cuts j and the two directions.

Statement

theorem spider_blocked_two_three_level_five_options (n : ℕ) :
    spider_gamma (n + 1) CentreStatus.none
        [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] =
      nat_mex_list
        [ 0 ^^^ spider_gamma n CentreStatus.incoming [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.outgoing [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(4, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],
          2 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
          2 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
          1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],
          0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)] ]
Source
step towards spider_blocked_two_three_level_five
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_rhoThe function spider_rho takes h : ℕ and delta, phi : SpiderLegEnd, returning h if phi = free; if phi = inward, it returns h % 2 when delta…
  • 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_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
  • 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 theorem performs one unfolding step of the recursion for the level-5 root state with centre status `none` and legs of lengths 5 (inward), 2 (free), and 3 (free). After rewriting with the recursive definition of `spider_gamma` and removing the outer `nat_mex_list` via `congr_arg`, the goal reduces to showing that the generated list of options equals the specified 19-element list. The proof expands the iteration over the three legs and their explicit cut ranges `List.range 5`, `List.range 2`, and `List.range 3`, and then finishes by finite evaluation with `simp` using `spider_rho` and `spider_update_centre`.

  1. Unfolding `spider_gamma` reduces the equality to showing that the generated list of move options matches the explicit 19-element list.

    Rewriting with `spider_gamma.eq_def` and simplifying the pattern matching reduces the left-hand side to `nat_mex_list` applied to the options generated for fuel $n$, centre status `none`, and the given three legs. Applying `congr_arg` with `nat_mex_list` removes the outer mex operator, leaving the goal of proving equality between the generated options list and the target 19-element list.

    lines 25–27

    uses spider_gamma.eq_def, congr_arg

      rw [spider_gamma.eq_def]
      dsimp only
      apply congr_arg nat_mex_list
  2. The options list decomposes into the concatenation of the options generated by each of the three legs.

    The definition indexes the three legs via `zipIdx`, producing `[((5, inward), 0), ((2, free), 1), ((3, free), 2)]`. Rewriting with `List.flatMap_cons` for each of the three elements and `List.flatMap_nil` for the empty tail expands the outer list flatMap into three concatenated lists, and `dsimp only` simplifies the pair projections and index-based removals (`eraseIdx`).

    lines 28–31

    uses List.flatMap_cons, List.flatMap_nil

      change List.flatMap _
          [((5, SpiderLegEnd.inward), 0), ((2, SpiderLegEnd.free), 1), ((3, SpiderLegEnd.free), 2)] = _
      rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil]
      dsimp only
  3. The cut ranges `List.range h` for legs of lengths 5, 2, and 3 are replaced by their explicit lists of indices.

    The cut loop iterates over `List.range h` for each leg. The proof establishes by reflexivity (`rfl`) that `List.range 5 = [0, 1, 2, 3, 4]`, `List.range 2 = [0, 1]`, and `List.range 3 = [0, 1, 2]`. Rewriting with these identities substitutes concrete index lists into each of the three sublists.

    lines 32–35

      have hr5 : List.range 5 = [0, 1, 2, 3, 4] := rfl
      have hr2 : List.range 2 = [0, 1] := rfl
      have hr3 : List.range 3 = [0, 1, 2] := rfl
      rw [hr5, hr2, hr3]
  4. Evaluating the cuts and leg orientations generates exactly the 19 target options, completing the proof.

    The `simp` tactic unfolds the definitions of `spider_rho` and `spider_update_centre` and computes all finite loop cases. The length-5 inward leg generates 9 valid moves (2 directions for cut lengths 1 to 4, and 1 direction for cut length 5 because the opposite direction is filtered out); the length-2 free leg generates 4 moves (2 cut lengths $\times$ 2 directions); and the length-3 free leg generates 6 moves (3 cut lengths $\times$ 2 directions). Computing the XOR coefficients and the updated game states for all $9 + 4 + 6 = 19$ cases confirms that the resulting list matches the right-hand side exactly.

    line 36

      simp [spider_rho, spider_update_centre]
spider_gamma.eq_def
The defining equation of `spider_gamma`, which unwinds the recursive evaluation at fuel $n+1$ into `nat_mex_list` applied to the list of available game options.
congr_arg
Equality is preserved under function application: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
List.flatMap_cons
Mapping and flattening over a non-empty list `x :: xs` equals the list `f x` concatenated with the flat map over `xs`.
List.flatMap_nil
Mapping and flattening over the empty list `[]` produces the empty list `[]`.

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 19-option list of the level-5 root state, at symbolic fuel n+1. -/theorem spider_blocked_two_three_level_five_options (n : ℕ) :    spider_gamma (n + 1) CentreStatus.none        [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] =      nat_mex_list        [ 0 ^^^ spider_gamma n CentreStatus.incoming [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.outgoing [(2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(3, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(4, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (3, SpiderLegEnd.free)],          2 ^^^ spider_gamma n CentreStatus.incoming [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],          2 ^^^ spider_gamma n CentreStatus.outgoing [(5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],          1 ^^^ spider_gamma n CentreStatus.none [(1, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.inward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)],          0 ^^^ spider_gamma n CentreStatus.none [(2, SpiderLegEnd.outward), (5, SpiderLegEnd.inward), (2, SpiderLegEnd.free)] ] := by  rw [spider_gamma.eq_def]  dsimp only  apply congr_arg nat_mex_list  change List.flatMap _      [((5, SpiderLegEnd.inward), 0), ((2, SpiderLegEnd.free), 1), ((3, SpiderLegEnd.free), 2)] = _  rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil]  dsimp only  have hr5 : List.range 5 = [0, 1, 2, 3, 4] := rfl  have hr2 : List.range 2 = [0, 1] := rfl  have hr3 : List.range 3 = [0, 1, 2] := rfl  rw [hr5, hr2, hr3]  simp [spider_rho, spider_update_centre]
See it in the graphDiscuss this resultChallenge it