spider_blocked_incoming_one_inward_options_nonempty
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.
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 `[]`.
simp
- The entire proof is executed in a single step by `simp`, which evaluates the list operations for the first leg of length 1, finding an explicit move and constructing a non-empty list without requiring any user-guided case splits or lemmas.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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