AFTD Auto-Formalizing Theoretical Domains

spider_blocked_incoming_one_inward_options_nonempty

theoremverified

The options list generated by [(1, inward), (r, φ)] at incoming centre is non-empty.

Statement

theorem spider_blocked_incoming_one_inward_options_nonempty (r : ℕ) (φ : SpiderLegEnd) :
    ([(1, SpiderLegEnd.inward), (r, φ)].zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ =>
      let rest := [(1, SpiderLegEnd.inward), (r, φ)].eraseIdx idx
      (List.range h).flatMap (fun j_zero =>
        let j := j_zero + 1
        [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta =>
          if j == h ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then none
          else
            let d := spider_rho (h - j) delta phi
            if j ≥ 2 then
              let new_L := (j - 1, delta) :: rest
              some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L)
            else
              let new_s := spider_update_centre CentreStatus.incoming delta
              some (d ^^^ spider_gamma (r + 1) new_s rest)
        )
      )
    )) ≠ []
Source
step towards spider_blocked_incoming_one_inward
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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_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…
  • spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…

The proof, explained

The theorem states that the list of options generated from the configuration [(1, inward), (r, φ)] with incoming centre status is non-empty. The proof proceeds by direct simplification: evaluating the transition rules on the first leg (1, inward) with cut length j = 1 and direction inward yields a valid option, because the blocking condition requires delta ≠ phi. Since the first leg produces at least one transition, the resulting list starts with a cons cell and is therefore non-empty, which the `simp` tactic verifies by computation.

  1. The list of options is non-empty. automation

    The simplifier `simp` evaluates the list operations (`flatMap`, `range`, and `filterMap`) on the concrete first element of the list, `(1, SpiderLegEnd.inward)`. For this leg of length 1, the only index in `List.range 1` is `j_zero = 0`, giving `j = 1`. Testing direction `delta = SpiderLegEnd.inward` avoids the blocking condition because `delta == phi` (both are `inward`), yielding a valid transition `some (...)`. This places a concrete element at the head of the resulting list (`_ :: _`), which definitionally cannot equal the empty list `[]`.

    line 20

      simp

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 options list generated by [(1, inward), (r, φ)] at incoming centre is non-empty. -/theorem spider_blocked_incoming_one_inward_options_nonempty (r : ℕ) (φ : SpiderLegEnd) :    ([(1, SpiderLegEnd.inward), (r, φ)].zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ =>      let rest := [(1, SpiderLegEnd.inward), (r, φ)].eraseIdx idx      (List.range h).flatMap (fun j_zero =>        let j := j_zero + 1        [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta =>          if j == h ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then none          else            let d := spider_rho (h - j) delta phi            if j ≥ 2 then              let new_L := (j - 1, delta) :: rest              some (d ^^^ spider_gamma (r + 1) CentreStatus.incoming new_L)            else              let new_s := spider_update_centre CentreStatus.incoming delta              some (d ^^^ spider_gamma (r + 1) new_s rest)        )      )    )) ≠ [] := by  simp
See it in the graphDiscuss this resultChallenge it