spider_mex_incoming_one_outward_not_mem
The value r ^^^ 1 is not a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.
Statement
theorem spider_mex_incoming_one_outward_not_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : r ^^^ 1 ∉ ([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 4
- 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_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 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 proof establishes that the candidate mex value r ^^^ 1 does not belong to the options list of the spider configuration by partitioning the concatenated options list into three parts: an initial 3-element list, an intermediate list flat-mapped over indices i ∈ {1, ..., r - 2}, and a terminal singleton list. For each part, assuming membership yields an equality involving the spider invariant ρ, which is evaluated using the known values of ρ on positive leg lengths (where it takes values in {0, 1}) and on zero length (where it evaluates to 0). In every case, either the injectivity of bitwise XOR with 1 forces r to equal 0, 1, or i ≤ r - 2, or parity-based evaluation of r ^^^ 1 as r ± 1 leads to an immediate arithmetic impossibility, contradicting r ≥ 2.
It suffices to show that r ^^^ 1 does not belong to any of the three concatenated sublists comprising the options list.
The options list is constructed by concatenating three parts: an initial three-element list, an intermediate family of lists flat-mapped over indices in List.range (r - 2), and a terminal singleton list. Rewriting membership across list concatenation via List.mem_append and distributing negation over disjunction with not_or transforms the goal into proving non-membership in each part separately. The refine tactic splits this into three independent subgoals.
uses
List.mem_append,not_orsimp only [List.mem_append, not_or] refine ⟨⟨?_, ?_⟩, ?_⟩
r ^^^ 1 is not an element of the initial three-element list [r, spider_rho (r - 1) inward φ ^^^ 1, spider_rho (r - 1) outward φ ^^^ 1].
Assume for contradiction that r ^^^ 1 is in this list. Unfolding list membership with List.mem_cons, List.not_mem_nil, and or_false gives three possibilities: r ^^^ 1 = r, or r ^^^ 1 is one of the two ρ-values XORed with 1. Since r ≥ 2, we have 1 ≤ r - 1, so spider_rho_pair_values shows that the pair of inward and outward values of ρ at r - 1 is either (0, 1) or (1, 0). In either case: (1) if r ^^^ 1 = r, case analysis on the parity of r (Nat.even_or_odd) implies r + 1 = r when r is even (Nat.xor_one_of_even) or r - 1 = r when r is odd (Nat.xor_one_of_odd), both impossible; (2) if r ^^^ 1 = 0 ^^^ 1, the injectivity of (· ^^^ 1) from xor_left_involutive implies r = 0, contradicting r ≥ 2; (3) if r ^^^ 1 = 1 ^^^ 1, injectivity implies r = 1, again contradicting r ≥ 2.
uses
List.mem_cons,List.not_mem_nil,or_false,spider_rho_pair_values,Nat.even_or_odd,Nat.xor_one_of_even,Nat.xor_one_of_odd,xor_left_involutive· intro h simp only [List.mem_cons, List.not_mem_nil, or_false] at h have hh : 1 ≤ r - 1 := by omega rcases spider_rho_pair_values (r - 1) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩ · rw [h_in, h_out] at h rcases h with h1 | h2 | h3 · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h1; omega · rw [Nat.xor_one_of_odd ho] at h1; omega · have : r = 0 := (xor_left_involutive 1).injective h2 omega · have : r = 1 := (xor_left_involutive 1).injective h3 omega · rw [h_in, h_out] at h rcases h with h1 | h2 | h3 · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h1; omega · rw [Nat.xor_one_of_odd ho] at h1; omega · have : r = 1 := (xor_left_involutive 1).injective h2 omega · have : r = 0 := (xor_left_involutive 1).injective h3 omega
r ^^^ 1 is not an element of the intermediate list obtained by flat-mapping over idx ∈ List.range (r - 2).
Assume for contradiction that r ^^^ 1 is in the flat-mapped list (List.mem_flatMap). Then there is an index idx < r - 2 (List.mem_range) such that r ^^^ 1 is in the two-element list for i = idx + 1. Since idx < r - 2, we have i ≤ r - 2 and 1 ≤ r - 1 - i. By spider_rho_pair_values, the inward and outward values of ρ at r - 1 - i are {0, 1}. Simplifying with zero_xor, xor_comm, and xor_cancel_right reveals the two list elements to be i ^^^ 1 and i. If r ^^^ 1 = i ^^^ 1, injectivity of XOR (xor_left_involutive) implies r = i, which contradicts i ≤ r - 2 < r. If r ^^^ 1 = i, case analysis on the parity of r (Nat.even_or_odd) gives r + 1 = i (Nat.xor_one_of_even) or r - 1 = i (Nat.xor_one_of_odd), both of which contradict i ≤ r - 2.
uses
List.mem_flatMap,List.mem_range,List.mem_cons,List.not_mem_nil,or_false,spider_rho_pair_values,zero_xor,xor_comm,xor_cancel_right,xor_left_involutive,Nat.even_or_odd,Nat.xor_one_of_even,Nat.xor_one_of_odd· intro h rw [List.mem_flatMap] at h rcases h with ⟨idx, hidx, hmem⟩ rw [List.mem_range] at hidx simp only [List.mem_cons, List.not_mem_nil, or_false] at hmem let i := idx + 1 have hi : i ≤ r - 2 := by omega have hh : 1 ≤ r - 1 - i := by omega rcases spider_rho_pair_values (r - 1 - i) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩ · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem rcases hmem with h1 | h2 · have : r = i := (xor_left_involutive 1).injective h1 omega · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h2; omega · rw [Nat.xor_one_of_odd ho] at h2; omega · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem rcases hmem with h1 | h2 · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h1; omega · rw [Nat.xor_one_of_odd ho] at h1; omega · have : r = i := (xor_left_involutive 1).injective h2 omega
r ^^^ 1 is not an element of the singleton list [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)].
Assume for contradiction that r ^^^ 1 is in the singleton list (List.mem_singleton). Because φ ≠ free, spider_rho_zero_same gives ρ(0, φ, φ) = 0, so the list element simplifies via zero_xor to (r - 1) ^^^ 1. The equation r ^^^ 1 = (r - 1) ^^^ 1 implies r = r - 1 by injectivity of XOR (xor_left_involutive). Linear arithmetic (omega) derives a contradiction from r = r - 1, completing the proof.
uses
List.mem_singleton,spider_rho_zero_same,zero_xor,xor_left_involutive· intro h simp only [List.mem_singleton] at h rw [spider_rho_zero_same φ hφ, zero_xor] at h have : r = r - 1 := (xor_left_involutive 1).injective h omega
List.mem_append- An element belongs to the concatenation of two lists if and only if it belongs to the first list or the second list.
not_or- The negation of a disjunction is equivalent to the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
List.mem_cons- An element belongs to a prepended list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil- No element belongs to the empty list.
or_false- A proposition disjoined with False is equivalent to the proposition itself: (p ∨ False) ↔ p.
spider_rho_pair_values- For any leg length h ≥ 1 and non-free end-condition φ, the pair of values (ρ(h, inward, φ), ρ(h, outward, φ)) is either (0, 1) or (1, 0).
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.
Nat.xor_one_of_odd- For an odd natural number n, n ^^^ 1 = n - 1.
xor_left_involutive- Bitwise XOR with a fixed value is an involution, and in particular is an injective function.
List.mem_flatMap- An element belongs to List.flatMap f l if and only if it belongs to f(a) for some a in l.
List.mem_range- A natural number m belongs to List.range n if and only if m < n.
zero_xor- Bitwise XOR of 0 with any element a is equal to a (0 ^^^ a = a).
xor_comm- Bitwise XOR is commutative: a ^^^ b = b ^^^ a.
xor_cancel_right- Bitwise XOR with the same value twice cancels out: (a ^^^ b) ^^^ b = a.
List.mem_singleton- An element belongs to the singleton list [b] if and only if it equals b.
spider_rho_zero_same- For length 0 and identical non-free leg end conditions φ, ρ(0, φ, φ) = 0.
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 candidate mex value r ^^^ 1 is not an element of the options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}). -/theorem spider_mex_incoming_one_outward_not_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : r ^^^ 1 ∉ ([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 simp only [List.mem_append, not_or] refine ⟨⟨?_, ?_⟩, ?_⟩ · intro h simp only [List.mem_cons, List.not_mem_nil, or_false] at h have hh : 1 ≤ r - 1 := by omega rcases spider_rho_pair_values (r - 1) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩ · rw [h_in, h_out] at h rcases h with h1 | h2 | h3 · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h1; omega · rw [Nat.xor_one_of_odd ho] at h1; omega · have : r = 0 := (xor_left_involutive 1).injective h2 omega · have : r = 1 := (xor_left_involutive 1).injective h3 omega · rw [h_in, h_out] at h rcases h with h1 | h2 | h3 · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h1; omega · rw [Nat.xor_one_of_odd ho] at h1; omega · have : r = 1 := (xor_left_involutive 1).injective h2 omega · have : r = 0 := (xor_left_involutive 1).injective h3 omega · intro h rw [List.mem_flatMap] at h rcases h with ⟨idx, hidx, hmem⟩ rw [List.mem_range] at hidx simp only [List.mem_cons, List.not_mem_nil, or_false] at hmem let i := idx + 1 have hi : i ≤ r - 2 := by omega have hh : 1 ≤ r - 1 - i := by omega rcases spider_rho_pair_values (r - 1 - i) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩ · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem rcases hmem with h1 | h2 · have : r = i := (xor_left_involutive 1).injective h1 omega · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h2; omega · rw [Nat.xor_one_of_odd ho] at h2; omega · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem rcases hmem with h1 | h2 · rcases Nat.even_or_odd r with he | ho · rw [Nat.xor_one_of_even he] at h1; omega · rw [Nat.xor_one_of_odd ho] at h1; omega · have : r = i := (xor_left_involutive 1).injective h2 omega · intro h simp only [List.mem_singleton] at h rw [spider_rho_zero_same φ hφ, zero_xor] at h have : r = r - 1 := (xor_left_involutive 1).injective h omega