spider_none_one_inward_one_outward_opts_not_mem
For r ≥ 2 and φ ≠ free, the level r is not a member of the closed-form option list of the κ₁ family.
Statement
theorem spider_none_one_inward_one_outward_opts_not_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
r ∉ 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
We prove by contradiction that r is not an element of the closed-form option list of the κ₁ family for r ≥ 2 and φ ≠ free by ruling out each option in the list. First, r ⊕ 1 ≠ r because XOR with 1 flips the least significant bit. Second, the single-step options ρ(r - 1, d, φ) for d ∈ {inward, outward} are at most 1, which cannot equal r ≥ 2. Third, for each a < r - 2, the compound options ρ(r - 2 - a, d, φ) ⊕ (a + 1) are bounded by (a + 1) + 1 = a + 2 < r, since ρ ≤ 1 and x ⊕ n ≤ n + 1 whenever x ≤ 1. Finally, r - 1 < r, so none of the options can equal r.
Bitwise XOR with 1 never fixes a number: a ⊕ 1 ≠ a for any natural number a.
Assume for contradiction that a ⊕ 1 = a. Applying `congrArg` with the function testing bit 0 shows that the 0-th bit of a ⊕ 1 equals the 0-th bit of a. Since the 0-th bit of a ⊕ 1 is the boolean XOR of the 0-th bit of a with the 0-th bit of 1 (which is true), this reduces to ¬(a.testBit 0) = a.testBit 0, a contradiction.
uses
congrArg,Nat.testBit_xorintro h have h2 := congrArg (fun n => n.testBit 0) h simp only [Nat.testBit_xor] at h2 simp at h2
For any leg height h ≥ 1, non-free end φ ≠ free, and direction d ∈ {inward, outward}, ρ(h, d, φ) ≤ 1.
By `spider_rho_pair_values`, the pair (ρ(h, inward, φ), ρ(h, outward, φ)) evaluates to either (0, 1) or (1, 0). In either case, both values are at most 1, so ρ(h, d, φ) ≤ 1 regardless of whether d is inward or outward.
uses
spider_rho_pair_valuesrcases spider_rho_pair_values h hh φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rcases hd with rfl | rfl <;> omega · rcases hd with rfl | rfl <;> omega
If x ≤ 1, then x ⊕ n ≤ n + 1 for any natural number n.
We perform a case split on x ≤ 1. If x = 0, 0 ⊕ n = n ≤ n + 1. If x = 1, by commutativity of XOR we consider n ⊕ 1: if n is even, n ⊕ 1 = n + 1 ≤ n + 1; if n is odd, n ⊕ 1 = n - 1 ≤ n + 1. Thus the inequality holds in all cases.
uses
Nat.xor_comm,Nat.even_or_odd,Nat.xor_one_of_even,Nat.xor_one_of_oddinterval_cases x · simp · rw [Nat.xor_comm] rcases Nat.even_or_odd n with h | h · rw [Nat.xor_one_of_even h] · rw [Nat.xor_one_of_odd h]; omega
To show r is not in the option list, it suffices to show r cannot equal any element produced by the list definition.
We expand the definition of `spider_none_one_inward_one_outward_opts` and simplify list membership across append, cons, flatMap, and range. Assuming for contradiction that r is in the list, we split into cases according to which option r could equal.
uses
List.mem_append,List.mem_cons,List.mem_flatMap,List.mem_range,List.not_mem_nil,List.cons_append,List.nil_appendrw [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, List.cons_append, List.nil_append] rintro (h | h | h | h | ⟨a, ha, h | h | h⟩ | h | h)
The level r cannot equal the first two options, which are r ⊕ 1.
In each of the first two cases, we have r = r ⊕ 1. We apply `spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne` to derive a contradiction, since XOR with 1 never fixes any number.
uses
spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne· exact spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne r h.symm · exact spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne r h.symm
The level r cannot equal the single-step options ρ(r - 1, inward, φ) or ρ(r - 1, outward, φ).
Since r ≥ 2, the height r - 1 is at least 1. Applying `spider_none_one_inward_one_outward_opts_not_mem_rho_le_one` shows that ρ(r - 1, d, φ) ≤ 1 for both d = inward and d = outward. Since r ≥ 2, this contradicts r = ρ(r - 1, d, φ), as discharged by linear arithmetic (`omega`).
uses
spider_none_one_inward_one_outward_opts_not_mem_rho_le_one· have := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 1) (by omega) φ hφ SpiderLegEnd.inward (Or.inl rfl) omega · have := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 1) (by omega) φ hφ SpiderLegEnd.outward (Or.inr rfl) omega
For any index a < r - 2, the level r cannot equal ρ(r - 2 - a, d, φ) ⊕ (a + 1) for d ∈ {inward, outward}.
Since a < r - 2, the remaining height r - 2 - a is at least 1, so `spider_none_one_inward_one_outward_opts_not_mem_rho_le_one` implies ρ(r - 2 - a, d, φ) ≤ 1 for both inward and outward directions. Applying `spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ` with this bound yields ρ(r - 2 - a, d, φ) ⊕ (a + 1) ≤ (a + 1) + 1 = a + 2. Because a < r - 2, we have a + 2 < r, so the option value is strictly less than r, giving a contradiction via linear arithmetic (`omega`).
uses
spider_none_one_inward_one_outward_opts_not_mem_rho_le_one,spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ· have hb := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 2 - a) (by omega) φ hφ SpiderLegEnd.inward (Or.inl rfl) have := spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ (spider_rho (r - 2 - a) SpiderLegEnd.inward φ) (a + 1) hb omega · have hb := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 2 - a) (by omega) φ hφ SpiderLegEnd.outward (Or.inr rfl) have := spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ (spider_rho (r - 2 - a) SpiderLegEnd.outward φ) (a + 1) hb omega
The remaining options (vacuous branches and r - 1) are impossible.
The empty tails of the flattened lists produce vacuous `False` hypotheses, each eliminated immediately. The final option is r - 1; since r ≥ 2, the equality r = r - 1 is impossible by linear arithmetic (`omega`).
· exact h.elim · omega · exact h
congrArg- Equal arguments produce equal values under any function: if a₁ = a₂, then f(a₁) = f(a₂).
Nat.testBit_xor- The i-th bit of x ⊕ y is the boolean XOR of the i-th bit of x and the i-th bit of y.
spider_rho_pair_values- For any leg height h ≥ 1 and non-free end φ, the pair of values (ρ(h, inward, φ), ρ(h, outward, φ)) is either (0, 1) or (1, 0).
Nat.xor_comm- Bitwise XOR on natural numbers is commutative: x ⊕ y = y ⊕ x.
Nat.even_or_odd- Every natural number is either even or odd.
Nat.xor_one_of_even- If n is even, then n ⊕ 1 = n + 1.
Nat.xor_one_of_odd- If n is odd, then n ⊕ 1 = n - 1.
List.mem_append- An element belongs to the concatenation s ++ t if and only if it belongs to s or to t.
List.mem_cons- An element belongs to b :: l if and only if it equals the head b or belongs to the tail l.
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.
List.not_mem_nil- No element belongs to the empty list.
List.cons_append- Prepending an element and appending lists satisfies (a :: as) ++ bs = a :: (as ++ bs).
List.nil_append- Appending any list to the empty list leaves it unchanged: [] ++ as = as.
spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne- Bitwise XOR with 1 never leaves a number unchanged: for all natural numbers a, a ⊕ 1 ≠ a.
spider_none_one_inward_one_outward_opts_not_mem_rho_le_one- For any height h ≥ 1, non-free end φ, and direction d ∈ {inward, outward}, ρ(h, d, φ) ≤ 1.
spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ- If a natural number x is at most 1, then x ⊕ n ≤ n + 1 for any natural number n.
- The expansion of membership in the concatenated option list generates vacuous `False` hypotheses corresponding to empty list tails, which are discharged by `False.elim` on lines 52 and 54.
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.
/-- Xor with 1 changes the lowest bit, so it never fixes a number. -/lemma spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne (a : ℕ) : a ^^^ 1 ≠ a := by intro h have h2 := congrArg (fun n => n.testBit 0) h simp only [Nat.testBit_xor] at h2 simp at h2/-- For a nonzero leg height and a non-free end, every `spider_rho` value for the twodirections is `0` or `1`. -/lemma spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (h : ℕ) (hh : 1 ≤ h) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) (d : SpiderLegEnd) (hd : d = SpiderLegEnd.inward ∨ d = SpiderLegEnd.outward) : spider_rho h d φ ≤ 1 := by rcases spider_rho_pair_values h hh φ hφ with ⟨h1, h2⟩ | ⟨h1, h2⟩ · rcases hd with rfl | rfl <;> omega · rcases hd with rfl | rfl <;> omega/-- Xoring a number at most `1` with `n` increases it by at most one. -/lemma spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ (x n : ℕ) (hx : x ≤ 1) : x ^^^ n ≤ n + 1 := by interval_cases x · simp · rw [Nat.xor_comm] rcases Nat.even_or_odd n with h | h · rw [Nat.xor_one_of_even h] · rw [Nat.xor_one_of_odd h]; omega/-- The value r itself is absent from the closed-form option list. -/theorem spider_none_one_inward_one_outward_opts_not_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : r ∉ spider_none_one_inward_one_outward_opts r φ := by 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, List.cons_append, List.nil_append] rintro (h | h | h | h | ⟨a, ha, h | h | h⟩ | h | h) · exact spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne r h.symm · exact spider_none_one_inward_one_outward_opts_not_mem_xor_one_ne r h.symm · have := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 1) (by omega) φ hφ SpiderLegEnd.inward (Or.inl rfl) omega · have := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 1) (by omega) φ hφ SpiderLegEnd.outward (Or.inr rfl) omega · have hb := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 2 - a) (by omega) φ hφ SpiderLegEnd.inward (Or.inl rfl) have := spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ (spider_rho (r - 2 - a) SpiderLegEnd.inward φ) (a + 1) hb omega · have hb := spider_none_one_inward_one_outward_opts_not_mem_rho_le_one (r - 2 - a) (by omega) φ hφ SpiderLegEnd.outward (Or.inr rfl) have := spider_none_one_inward_one_outward_opts_not_mem_xor_le_succ (spider_rho (r - 2 - a) SpiderLegEnd.outward φ) (a + 1) hb omega · exact h.elim · omega · exact h