spider_none_one_inward_one_outward_opts_all_lt_mem
For r ≥ 2 and φ ≠ free, every k < r is a member of the closed-form option list of the κ₁ family.
Statement
theorem spider_none_one_inward_one_outward_opts_all_lt_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
∀ k < r, k ∈ spider_none_one_inward_one_outward_opts r φ- Source
- step towards spider_blocked_none_one_inward_one_outward
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- spider_none_one_inward_one_outward_optsThe explicit closed-form option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after substituting the sub-state values: the two…
- 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).
- 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_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 2
- spider_none_one_inward_one_outward_opts_mexFor r ≥ 2 and φ ≠ free, the mex of the explicit option list of the κ₁ configuration equals r.
- spider_blocked_none_one_inward_one_outwardFor the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
The proof, explained
The theorem states that every natural number k < r belongs to the options list spider_none_one_inward_one_outward_opts r φ when r ≥ 2 and φ ≠ free. The proof unfolds the definition of the options list and applies spider_rho_pair_values, which guarantees that at any positive height, exactly one of the inward and outward leg rho values is 0 and the other is 1. Membership is then established by case analysis on k: numbers k < 2 correspond to the explicit values 0 and 1 in the initial segment; k = r - 1 matches the trailing element of the list; and for intermediate values 2 ≤ k ≤ r - 2, choosing index a = k - 1 produces an option where the zero rho value yields 0 ^^^ (a + 1) = k.
Fix k < r and note that r - 1 ≥ 1.
We introduce an arbitrary natural number k satisfying k < r. Because r ≥ 2, linear arithmetic (via omega) gives r - 1 ≥ 1.
intro k hk have hr1 : 1 ≤ r - 1 := by omega
Expanding the definition of the options list reduces membership to showing k is an explicit initial element (0, 1, or r ^^^ 1), matches the trailing element r - 1, or is produced by the intermediate flatMap range.
Applying spider_rho_pair_values at height r - 1 shows that one of the inward and outward values of spider_rho is 0 and the other is 1. Unfolding spider_none_one_inward_one_outward_opts and simplifying list membership via List.mem_append, List.mem_cons, List.mem_flatMap, List.mem_range, List.not_mem_nil, and or_false reduces the goal in both parity branches to a disjunction over the elements of the options list.
uses
spider_rho_pair_values,List.mem_append,List.mem_cons,List.mem_flatMap,List.mem_range,List.not_mem_nil,or_falsercases spider_rho_pair_values (r - 1) hr1 φ hφ with ⟨h0, h1⟩ | ⟨h1, h0⟩ <;> rw [spider_none_one_inward_one_outward_opts] <;> simp only [List.mem_append, List.mem_cons, List.mem_flatMap, List.mem_range, List.not_mem_nil, or_false, h0, h1]
In the first parity case (inward rho is 0, outward rho is 1), membership holds when k < 2.
Using Nat.lt_or_ge, we split into cases k < 2 and k ≥ 2. When k < 2, k is either 0 or 1 (interval_cases). Since both 0 and 1 are present in the options list, simp closes each subcase by reflexivity.
uses
Nat.lt_or_ge· rcases Nat.lt_or_ge k 2 with hlt2 | hge2 · interval_cases k <;> simp
When k ≥ 2 and k = r - 1, membership holds via the final element of the list.
We split on whether k = r - 1. When it is, k directly matches the final singleton [r - 1] in the options list, closing the goal with Or.inr.
uses
Or.inr· by_cases hkr : k = r - 1 · exact Or.inr hkr
When 2 ≤ k ≤ r - 2, k is obtained from the flatMap segment at index a = k - 1.
Since k < r and k ≠ r - 1, we have k ≤ r - 2 and therefore r - 1 - k ≥ 1. By spider_rho_pair_values at height r - 1 - k, one of the two leg orientations has rho value 0. Choosing index a = k - 1 < r - 2, the remaining height is r - 2 - a = r - 1 - k. Selecting the leg orientation whose rho is 0, the option value evaluates to 0 ^^^ (a + 1) = (k - 1) + 1 = k by Nat.zero_xor and linear arithmetic.
uses
spider_rho_pair_values,Or.inl,Or.inr,Nat.zero_xor· have hle : k ≤ r - 2 := by omega rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩ · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega
In the second parity case (inward rho is 1, outward rho is 0), membership holds when k < 2.
As in the first case, case splitting with Nat.lt_or_ge leaves k = 0 and k = 1, both of which appear in the options list and are discharged by interval_cases and simp.
uses
Nat.lt_or_ge· rcases Nat.lt_or_ge k 2 with hlt2 | hge2 · interval_cases k <;> simp
When k ≥ 2 and k = r - 1, membership holds via the final element of the list.
If k = r - 1, k matches the trailing element [r - 1] of the options list, closing the goal via Or.inr.
uses
Or.inr· by_cases hkr : k = r - 1 · exact Or.inr hkr
When 2 ≤ k ≤ r - 2, k is obtained from the flatMap segment at index a = k - 1.
Just as in the first parity branch, k ≤ r - 2 implies r - 1 - k ≥ 1. Applying spider_rho_pair_values at height r - 1 - k and picking index a = k - 1 < r - 2, the branch with rho = 0 simplifies via Nat.zero_xor to 0 ^^^ (a + 1) = k.
uses
spider_rho_pair_values,Or.inl,Or.inr,Nat.zero_xor· have hle : k ≤ r - 2 := by omega rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩ · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega
spider_rho_pair_values- For any height h ≥ 1 and any non-free leg end φ, exactly one of the inward and outward leg values of spider_rho is 0 and the other is 1.
List.mem_append- An element belongs to the concatenation of two lists s ++ t if and only if it belongs to s or to t.
List.mem_cons- An element a belongs to b :: l if and only if a = b or a ∈ l.
List.mem_flatMap- An element b belongs to flatMap f l if and only if there is an element a ∈ l such that b ∈ f a.
List.mem_range- A natural number m belongs to List.range n if and only if m < n.
List.not_mem_nil- No element belongs to the empty list [].
or_false- For any proposition p, (p ∨ False) is logically equivalent to p.
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
Or.inr- If b holds, then the disjunction a ∨ b holds (right injection).
Or.inl- If a holds, then the disjunction a ∨ b holds (left injection).
Nat.zero_xor- Zero is the identity element for bitwise XOR on natural numbers: 0 ^^^ x = x.
- The case split on spider_rho_pair_values at height r - 1 generates two symmetric cases depending on which of inward or outward rho is 0. The Lean proof repeats the exact same 12-line argument in both branches (lines 10–21 and lines 22–33) because the options list contains both 0 and 1 as well as both leg options at each index.
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.
/-- Every natural number below r occurs in the closed-form option list. -/theorem spider_none_one_inward_one_outward_opts_all_lt_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : ∀ k < r, k ∈ spider_none_one_inward_one_outward_opts r φ := by intro k hk have hr1 : 1 ≤ r - 1 := by omega rcases spider_rho_pair_values (r - 1) hr1 φ hφ with ⟨h0, h1⟩ | ⟨h1, h0⟩ <;> rw [spider_none_one_inward_one_outward_opts] <;> simp only [List.mem_append, List.mem_cons, List.mem_flatMap, List.mem_range, List.not_mem_nil, or_false, h0, h1] · rcases Nat.lt_or_ge k 2 with hlt2 | hge2 · interval_cases k <;> simp · by_cases hkr : k = r - 1 · exact Or.inr hkr · have hle : k ≤ r - 2 := by omega rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩ · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega · rcases Nat.lt_or_ge k 2 with hlt2 | hge2 · interval_cases k <;> simp · by_cases hkr : k = r - 1 · exact Or.inr hkr · have hle : k ≤ r - 2 := by omega rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩ · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩) have harg : r - 2 - (k - 1) = r - 1 - k := by omega rw [harg, g0, Nat.zero_xor]; omega