spider_mex_incoming_one_outward_all_lt_mem
Every natural number k < r ^^^ 1 is a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.
Statement
theorem spider_mex_incoming_one_outward_all_lt_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : ∀ k < r ^^^ 1, k ∈ ([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)])
- Source
- step towards spider_mex_incoming_one_outward
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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 1
- spider_mex_incoming_one_outwardThe minimum excluded value of the explicit options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2…
The proof, explained
The theorem shows that every k < r ^^^ 1 is contained in the options list by decomposing the list into a head `L_head`, a flat-mapped body `L_flat`, and a tail `L_tail`. Using `spider_rho_pair_values`, the head contains {0, 1, r}, while the body contains both i and i ^^^ 1 for each intermediate value 1 ≤ i ≤ r - 2. When r is even, r ^^^ 1 = r + 1, and every k ≤ r is either in the head (values 0, 1, r), in the body via the XOR companion (r - 1 = (r - 2) ^^^ 1), or in the body directly (2 ≤ k ≤ r - 2). When r is odd, r ^^^ 1 = r - 1, and every k ≤ r - 2 is either 0 or 1 (in the head) or between 2 and r - 2 (in the body).
The options list is partitioned into three sublists: `L_head`, `L_flat`, and `L_tail`.
We define `L_head` as the initial three-element list consisting of r and the two XORed values of `spider_rho (r - 1)` with 1, `L_flat` as the flat-mapped list containing the pairs for intermediate indices i ∈ {1, ..., r - 2}, and `L_tail` as the final singleton list.
let L_head := [r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] let L_flat := (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)]) let L_tail := [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)]
The numbers 0, 1, and r are all members of `L_head`.
Since r ≥ 2, the leg length r - 1 is at least 1. By `spider_rho_pair_values`, the inward and outward values of `spider_rho` at height r - 1 evaluate to {0, 1} in some order. XORing these with 1 gives 0 ^^^ 1 = 1 and 1 ^^^ 1 = 0, so both 0 and 1 belong to `L_head`. Since r is explicitly the first element of `L_head`, all three values belong to `L_head`.
uses
spider_rho_pair_valueshave hh : 1 ≤ r - 1 := by omega have h_head : 0 ∈ L_head ∧ 1 ∈ L_head ∧ r ∈ L_head := by dsimp only [L_head] rcases spider_rho_pair_values (r - 1) hh φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; simp · rw [h1, h2]; simp
For every integer i with 1 ≤ i ≤ r - 2, the number i is an element of `L_flat`.
Given 1 ≤ i ≤ r - 2, the index idx = i - 1 belongs to `List.range (r - 2)` by `List.mem_range`. The two elements added at this step correspond to the inward and outward rho values at height r - 1 - i. Since r - 1 - i ≥ 1, `spider_rho_pair_values` ensures one rho value is 0 and the other is 1. The 0 term simplifies to 0 ^^^ (i ^^^ 1) = i ^^^ 1 by `zero_xor`, while the 1 term simplifies to 1 ^^^ (i ^^^ 1) = (1 ^^^ 1) ^^^ i = i by `xor_comm` and `xor_cancel_right`. Hence i appears in `L_flat` by `List.mem_flatMap`.
uses
List.mem_flatMap,List.mem_range,spider_rho_pair_values,zero_xor,xor_comm,xor_cancel_righthave h_flat_i : ∀ i, 1 ≤ i → i ≤ r - 2 → i ∈ L_flat := by intro i hi1 hi2 rw [List.mem_flatMap] refine ⟨i - 1, ?_, ?_⟩ · rw [List.mem_range]; omega · dsimp only have : i - 1 + 1 = i := by omega rw [this] have hhi : 1 ≤ r - 1 - i := by omega rcases spider_rho_pair_values (r - 1 - i) hhi φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp
For every integer i with 1 ≤ i ≤ r - 2, the number i ^^^ 1 is an element of `L_flat`.
By the exact same index selection idx = i - 1 and evaluation via `spider_rho_pair_values`, `zero_xor`, `xor_comm`, and `xor_cancel_right`, the two-element block produced in `L_flat` contains both i and i ^^^ 1. Therefore i ^^^ 1 ∈ `L_flat` as well.
uses
List.mem_flatMap,List.mem_range,spider_rho_pair_values,zero_xor,xor_comm,xor_cancel_righthave h_flat_xor : ∀ i, 1 ≤ i → i ≤ r - 2 → i ^^^ 1 ∈ L_flat := by intro i hi1 hi2 rw [List.mem_flatMap] refine ⟨i - 1, ?_, ?_⟩ · rw [List.mem_range]; omega · dsimp only have : i - 1 + 1 = i := by omega rw [this] have hhi : 1 ≤ r - 1 - i := by omega rcases spider_rho_pair_values (r - 1 - i) hhi φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp
To show k is in the options list for any k < r ^^^ 1, it suffices to show k ∈ `L_head ++ L_flat ++ L_tail`.
We introduce k together with the hypothesis k < r ^^^ 1, and restate the membership goal in terms of the concatenated sublists `L_head ++ L_flat ++ L_tail`.
intro k hk change k ∈ L_head ++ L_flat ++ L_tail
When r is even, every k < r ^^^ 1 belongs to the options list.
We split into cases on whether r is even or odd using `Nat.even_or_odd`. When r is even, `Nat.xor_one_of_even` gives r ^^^ 1 = r + 1, so k ≤ r. We branch on whether k < 2 or k ≥ 2 using `lt_or_ge`: - If k < 2, then k = 0 or k = 1, both of which belong to `L_head`. - If k ≥ 2, we split on k = r or k < r using `eq_or_lt_of_le`. If k = r, it is in `L_head`. - If k < r, then k ≤ r - 1. We split on k = r - 1 or k < r - 1 using `eq_or_lt_of_le`. - When k = r - 1, writing r = 2m, the number r - 2 = 2m - 2 is even, so (r - 2) ^^^ 1 = r - 1 by `Nat.xor_one_of_even`. Since 1 ≤ r - 2 ≤ r - 2, `h_flat_xor` with i = r - 2 shows that r - 1 ∈ `L_flat`. - When k < r - 1, we have 1 ≤ k ≤ r - 2, so k ∈ `L_flat` directly by `h_flat_i`.
uses
Nat.even_or_odd,Nat.xor_one_of_even,lt_or_ge,eq_or_lt_of_lercases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at hk rcases lt_or_ge k 2 with hk01 | hk2 · interval_cases k · simp [h_head.1] · simp [h_head.2.1] · rcases eq_or_lt_of_le (show k ≤ r by omega) with rfl | hkr · simp [h_head.2.2] · rcases eq_or_lt_of_le (show k ≤ r - 1 by omega) with rfl | hkr' · rcases he with ⟨m, rfl⟩ have he' : Even (m + m - 2) := ⟨m - 1, by omega⟩ have h_xor : (m + m - 2) ^^^ 1 = m + m - 1 := by rw [Nat.xor_one_of_even he'] omega have h_mem : m + m - 1 ∈ L_flat := by rw [← h_xor] exact h_flat_xor (m + m - 2) (by omega) (by omega) simp [h_mem] · have h_mem : k ∈ L_flat := h_flat_i k (by omega) (by omega) simp [h_mem]
When r is odd, every k < r ^^^ 1 belongs to the options list.
When r is odd, `Nat.xor_one_of_odd` gives r ^^^ 1 = r - 1, so k ≤ r - 2. We split on whether k < 2 or k ≥ 2 using `lt_or_ge`: - If k < 2, then k = 0 or k = 1, both belonging to `L_head`. - If k ≥ 2, then 1 ≤ k ≤ r - 2, so k ∈ `L_flat` by `h_flat_i`. This covers all cases and concludes the proof.
uses
Nat.xor_one_of_odd,lt_or_ge· rw [Nat.xor_one_of_odd ho] at hk rcases lt_or_ge k 2 with hk01 | hk2 · interval_cases k · simp [h_head.1] · simp [h_head.2.1] · have h_mem : k ∈ L_flat := h_flat_i k (by omega) (by omega) simp [h_mem]
spider_rho_pair_values- For any leg length h ≥ 1 and non-free terminal condition φ, exactly one of the values `spider_rho h inward φ` and `spider_rho h outward φ` is 0 and the other is 1.
List.mem_flatMap- An element b belongs to the flat map of f over l if and only if b ∈ f a for some a ∈ l.
List.mem_range- A natural number m belongs to `List.range n` if and only if m < n.
zero_xor- Zero is the identity for bitwise XOR: 0 ^^^ a = a.
xor_comm- Bitwise XOR is commutative: a ^^^ b = b ^^^ a.
xor_cancel_right- Bitwise XOR cancels on the right: (a ^^^ b) ^^^ b = a.
Nat.even_or_odd- Every natural number is either even or odd.
Nat.xor_one_of_even- For an even natural number n, n ^^^ 1 = n + 1.
lt_or_ge- In any linear order, either a < b or b ≤ a.
eq_or_lt_of_le- If a ≤ b in a partial order, then either a = b or a < b.
Nat.xor_one_of_odd- For an odd natural number n, n ^^^ 1 = n - 1.
- The singleton tail sublist `L_tail` is never used to match any `k`; all values `k < r ^^^ 1` are already contained in `L_head` or `L_flat`.
- Bounds checks and basic arithmetic equalities (such as `1 ≤ r - 1` and `(i - 1) + 1 = i`) are discharged automatically by `omega`.
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 strictly less than r ^^^ 1 is an element of the options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}). -/theorem spider_mex_incoming_one_outward_all_lt_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : ∀ k < r ^^^ 1, k ∈ ([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)]) := by let L_head := [r, spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ 1, spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ 1] let L_flat := (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)]) let L_tail := [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)] have hh : 1 ≤ r - 1 := by omega have h_head : 0 ∈ L_head ∧ 1 ∈ L_head ∧ r ∈ L_head := by dsimp only [L_head] rcases spider_rho_pair_values (r - 1) hh φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2]; simp · rw [h1, h2]; simp have h_flat_i : ∀ i, 1 ≤ i → i ≤ r - 2 → i ∈ L_flat := by intro i hi1 hi2 rw [List.mem_flatMap] refine ⟨i - 1, ?_, ?_⟩ · rw [List.mem_range]; omega · dsimp only have : i - 1 + 1 = i := by omega rw [this] have hhi : 1 ≤ r - 1 - i := by omega rcases spider_rho_pair_values (r - 1 - i) hhi φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp have h_flat_xor : ∀ i, 1 ≤ i → i ≤ r - 2 → i ^^^ 1 ∈ L_flat := by intro i hi1 hi2 rw [List.mem_flatMap] refine ⟨i - 1, ?_, ?_⟩ · rw [List.mem_range]; omega · dsimp only have : i - 1 + 1 = i := by omega rw [this] have hhi : 1 ≤ r - 1 - i := by omega rcases spider_rho_pair_values (r - 1 - i) hhi φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp · rw [h1, h2, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right]; simp intro k hk change k ∈ L_head ++ L_flat ++ L_tail rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at hk rcases lt_or_ge k 2 with hk01 | hk2 · interval_cases k · simp [h_head.1] · simp [h_head.2.1] · rcases eq_or_lt_of_le (show k ≤ r by omega) with rfl | hkr · simp [h_head.2.2] · rcases eq_or_lt_of_le (show k ≤ r - 1 by omega) with rfl | hkr' · rcases he with ⟨m, rfl⟩ have he' : Even (m + m - 2) := ⟨m - 1, by omega⟩ have h_xor : (m + m - 2) ^^^ 1 = m + m - 1 := by rw [Nat.xor_one_of_even he'] omega have h_mem : m + m - 1 ∈ L_flat := by rw [← h_xor] exact h_flat_xor (m + m - 2) (by omega) (by omega) simp [h_mem] · have h_mem : k ∈ L_flat := h_flat_i k (by omega) (by omega) simp [h_mem] · rw [Nat.xor_one_of_odd ho] at hk rcases lt_or_ge k 2 with hk01 | hk2 · interval_cases k · simp [h_head.1] · simp [h_head.2.1] · have h_mem : k ∈ L_flat := h_flat_i k (by omega) (by omega) simp [h_mem]