spider_mex_incoming_one_outward
The minimum excluded value of the explicit options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2 and φ ≠ free.
Statement
theorem spider_mex_incoming_one_outward (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : nat_mex_list ([r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] ++ (List.range (r - 2)).flatMap (fun idx => let i := idx + 1 [spider_rho (r - 1 - i) SpiderLegEnd.inward φ ^^^ (i ^^^ 1), spider_rho (r - 1 - i) SpiderLegEnd.outward φ ^^^ (i ^^^ 1)]) ++ [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)]) = r ^^^ 1
- Source
- step towards spider_blocked_incoming_one_outward
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- nat_mex_list_not_mem_and_ltFor a list l of naturals, nat_mex_list l is not a member of l, and every natural number below nat_mex_list l is a member of l.
- spider_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 0.
- spider_rho_pair_valuesFor every h ≥ 1 and φ ≠ free, the pair of rho values (spider_rho h inward φ, spider_rho h outward φ) is either (0, 1) or (1, 0).
- spider_mex_incoming_one_outward_not_memThe value r ^^^ 1 is not a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.
- spider_mex_incoming_one_outward_all_lt_memEvery natural number k < r ^^^ 1 is a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.
- 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…
- 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…
- Used by 1
- spider_blocked_incoming_one_outwardFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
The proof, explained
The proof determines the minimum excluded value (mex) of the option list by applying a general characterization lemma: if a candidate value does not appear in a list and all strictly smaller numbers do, then that value is the mex. The proof first establishes this criterion by trichotomy against the definition of mex, then applies two dedicated lemmas showing that r ^^^ 1 satisfies both conditions for the options list.
For any list l and natural number m, if m ∉ l and all k < m are in l, then the mex of l is m.
The characterizing property of the mex gives that nat_mex_list l ∉ l and all k < nat_mex_list l are in l. Applying trichotomy to nat_mex_list l and m rules out both strict inequalities: if nat_mex_list l < m, then nat_mex_list l ∈ l by the assumption on m, contradiction; if m < nat_mex_list l, then m ∈ l by the property of mex, contradicting m ∉ l. Hence nat_mex_list l = m.
uses
nat_mex_list_not_mem_and_lt,lt_trichotomyhave ⟨h1, h2⟩ := nat_mex_list_not_mem_and_lt l rcases lt_trichotomy (nat_mex_list l) m with hlt | heq | hgt · exact (h1 (h_all_lt (nat_mex_list l) hlt)).elim · exact heq · exact (h_not_mem (h2 m hgt)).elim
It suffices to show that r ^^^ 1 is not in the options list and that every k < r ^^^ 1 is in the list.
Applying the general mex characterization lemma spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem reduces the evaluation of the mex to verifying non-membership of r ^^^ 1 and membership of all smaller natural numbers.
uses
spider_mex_incoming_one_outward_of_not_mem_and_all_lt_memapply spider_mex_incoming_one_outward_of_not_mem_and_all_lt_memThe value r ^^^ 1 is not in the options list.
This is established by the lemma spider_mex_incoming_one_outward_not_mem.
uses
spider_mex_incoming_one_outward_not_mem· exact spider_mex_incoming_one_outward_not_mem r hr φ hφEvery natural number k < r ^^^ 1 belongs to the options list.
This is established by the lemma spider_mex_incoming_one_outward_all_lt_mem, completing the proof.
uses
spider_mex_incoming_one_outward_all_lt_mem· exact spider_mex_incoming_one_outward_all_lt_mem r hr φ hφ
nat_mex_list_not_mem_and_lt- For any list of natural numbers, its mex does not belong to the list, and every strictly smaller natural number belongs to the list.
lt_trichotomy- For any two elements a and b in a linear order, exactly one of a < b, a = b, or b < a holds.
spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem- If a natural number m is not in a list l and every k < m is in l, then the mex of l is m.
spider_mex_incoming_one_outward_not_mem- The value r ^^^ 1 does not belong to the explicit option list of the spider configuration.
spider_mex_incoming_one_outward_all_lt_mem- Every natural number strictly smaller than r ^^^ 1 belongs to the explicit option list of the spider configuration.
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.
lemma spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem (l : List ℕ) (m : ℕ) (h_not_mem : m ∉ l) (h_all_lt : ∀ k < m, k ∈ l) : nat_mex_list l = m := by have ⟨h1, h2⟩ := nat_mex_list_not_mem_and_lt l rcases lt_trichotomy (nat_mex_list l) m with hlt | heq | hgt · exact (h1 (h_all_lt (nat_mex_list l) hlt)).elim · exact heq · exact (h_not_mem (h2 m hgt)).elim/-- The mex of the explicit closed-form option list of the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2 and φ ≠ free. -/theorem spider_mex_incoming_one_outward (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : nat_mex_list ([r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] ++ (List.range (r - 2)).flatMap (fun idx => let i := idx + 1 [spider_rho (r - 1 - i) SpiderLegEnd.inward φ ^^^ (i ^^^ 1), spider_rho (r - 1 - i) SpiderLegEnd.outward φ ^^^ (i ^^^ 1)]) ++ [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)]) = r ^^^ 1 := by apply spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem · exact spider_mex_incoming_one_outward_not_mem r hr φ hφ · exact spider_mex_incoming_one_outward_all_lt_mem r hr φ hφ