spider_blocked_optionvals_le
For r ≥ 2 and β ≠ free, every element of the explicit options list of (in;{(r,β),(1,free)}) is at most r.
Statement
theorem spider_blocked_optionvals_le (r : ℕ) (hr : 2 ≤ r) (beta : SpiderLegEnd)
(hβ : beta ≠ SpiderLegEnd.free) : ∀ x ∈ spider_blocked_optionvals r beta, x ≤ r- Source
- step towards spider_two_leg_blocked_incoming_val
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- spider_blocked_optionvalsThe explicit options list of the state (in;{(r,β),(1,free)}) at fuel r + 2 after substituting the inductive closed forms: for each cut j =…
- spider_blocked_valThe conjectured closed form of the blocked two-leg family at incoming centre: for end condition inward it is m - 1 when m % 4 = 3 and m +…
- 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…
- spider_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
- 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_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 0.
- Used by 2
- spider_blocked_optionvals_not_memFor r ≥ 1 and β inward or outward, the closed-form value spider_blocked_val β r does not occur in the explicit options list of…
- spider_blocked_raw_opts_splitThe raw option list of (in;{(r,β),(1,free)}) decomposes as spider_blocked_leg0_opts r β ++ spider_blocked_free_leg_opts r β: the zipIdx…
The proof, explained
To show that every option value x in spider_blocked_optionvals r beta is at most r when r ≥ 2 and beta ≠ free, the proof decomposes the options list into three parts: the flatMap options, the middle singleton option, and the two trailing options. For each flatMap option, the value is an XOR of a rho component (bounded by 1 via spider_blocked_optionvals_le_rho_le_one) and a blocked leg value (bounded by idx + 1); their XOR is at most idx + 2 ≤ r. The middle singleton simplifies to a single blocked leg value bounded by (r - 1) + 1 = r because rho(0, beta, beta) vanishes. Finally, the trailing options are bounded by 1 ≤ r and evaluated directly to r ≤ r.
For every natural number b, b ^^^ 1 ≤ b + 1.
We split into cases on whether b is even or odd using `Nat.even_or_odd`. If b is even, `Nat.xor_one_of_even` gives b ^^^ 1 = b + 1 ≤ b + 1. If b is odd, `Nat.xor_one_of_odd` gives b ^^^ 1 = b - 1, which is at most b + 1 by linear arithmetic (`omega`).
uses
Nat.even_or_odd,Nat.xor_one_of_even,Nat.xor_one_of_oddlemma spider_blocked_optionvals_le_xor_one_le (b : ℕ) : b ^^^ 1 ≤ b + 1 := by rcases Nat.even_or_odd b with ⟨k, hk⟩ | ⟨k, hk⟩ · rw [Nat.xor_one_of_even ⟨k, hk⟩] · rw [Nat.xor_one_of_odd ⟨k, hk⟩] omega
If a ≤ 1, then a ^^^ b ≤ b + 1 for any natural number b.
We test the cases a = 0 and a = 1 using `interval_cases`. When a = 0, 0 ^^^ b = b ≤ b + 1 holds by simplification. When a = 1, by commutativity of XOR (`Nat.xor_comm`), 1 ^^^ b = b ^^^ 1, which is at most b + 1 by `spider_blocked_optionvals_le_xor_one_le`.
uses
Nat.xor_comm,spider_blocked_optionvals_le_xor_one_lelemma spider_blocked_optionvals_le_xor_le_succ (a b : ℕ) (ha : a ≤ 1) : a ^^^ b ≤ b + 1 := by interval_cases a · simp · rw [Nat.xor_comm]; exact spider_blocked_optionvals_le_xor_one_le b
For any height h, leg end delta, and beta ≠ free, spider_rho h delta beta ≤ 1.
We case-split on beta. The case beta = free is impossible by the assumption hβ. For beta = inward or beta = outward, unfolding `spider_rho` gives an if-then-else: if delta matches beta, the value is h % 2, which is strictly less than 2 by `Nat.mod_lt` (since 0 < 2) and therefore at most 1; otherwise, the value is either 1 or 0, both of which are at most 1.
uses
Nat.mod_ltlemma spider_blocked_optionvals_le_rho_le_one (h : ℕ) (delta beta : SpiderLegEnd) (hβ : beta ≠ SpiderLegEnd.free) : spider_rho h delta beta ≤ 1 := by rcases beta with _ | _ | _ · exact absurd rfl hβ · simp only [spider_rho] split_ifs with h1 h2 · have := Nat.mod_lt h (by norm_num : 0 < 2); omega · omega · omega · simp only [spider_rho] split_ifs with h1 h2 · have := Nat.mod_lt h (by norm_num : 0 < 2); omega · omega · omega
For any leg end phi ≠ free, spider_rho_star h phi = h.
By case analysis on phi: the free case contradicts the assumption hφ, and for inward or outward, `spider_rho_star` unfolds directly to h.
lemma spider_blocked_optionvals_le_rho_star_ne_free (h : ℕ) (phi : SpiderLegEnd) (hφ : phi ≠ SpiderLegEnd.free) : spider_rho_star h phi = h := by rcases phi with _ | _ | _ <;> simp [spider_rho_star] at *
For any leg end delta and natural number m, spider_blocked_val delta m ≤ m + 1.
By case analysis on delta and unfolding `spider_blocked_val`, the value is either m - 1 or m + 1, both of which are at most m + 1 by linear arithmetic (`omega`).
lemma spider_blocked_optionvals_le_val_le_succ (delta : SpiderLegEnd) (m : ℕ) : spider_blocked_val delta m ≤ m + 1 := by rcases delta with _ | _ | _ <;> simp only [spider_blocked_val] <;> split_ifs <;> omega
Membership of x in spider_blocked_optionvals r beta splits into the first two components versus the trailing two options.
We introduce an element x and the hypothesis hx that x ∈ spider_blocked_optionvals r beta. Unfolding `spider_blocked_optionvals`, the list is the concatenation of the flatMap options and a middle singleton option with the two trailing options. We split on membership in this outer concatenation using `List.mem_append.mp`.
uses
List.mem_append.mptheorem spider_blocked_optionvals_le (r : ℕ) (hr : 2 ≤ r) (beta : SpiderLegEnd) (hβ : beta ≠ SpiderLegEnd.free) : ∀ x ∈ spider_blocked_optionvals r beta, x ≤ r := by intro x hx simp only [spider_blocked_optionvals] at hx rcases List.mem_append.mp hx with hx | hx
Every option value arising from the flatMap list is at most r.
We split the first component into the flatMap and the middle singleton using `List.mem_append.mp`, focusing on the flatMap case. Using `List.mem_flatMap.mp`, `List.mem_range`, and `List.mem_map.mp`, x is of the form spider_rho (r - (idx + 1)) delta beta ^^^ spider_blocked_val delta idx for some idx < r - 1 and delta ∈ [inward, outward]. Lemma `spider_blocked_optionvals_le_rho_le_one` bounds the rho factor by 1, and `spider_blocked_optionvals_le_val_le_succ` bounds the blocked value by idx + 1. Lemma `spider_blocked_optionvals_le_xor_le_succ` then bounds their XOR by (idx + 1) + 1 = idx + 2. Since idx < r - 1, linear arithmetic (`omega`) shows x ≤ r.
uses
List.mem_append.mp,List.mem_flatMap.mp,List.mem_range,List.mem_map.mp,spider_blocked_optionvals_le_rho_le_one,spider_blocked_optionvals_le_val_le_succ,spider_blocked_optionvals_le_xor_le_succ· rcases List.mem_append.mp hx with hx | hx · rcases List.mem_flatMap.mp hx with ⟨idx, hidx, hx⟩ simp only [List.mem_range] at hidx rcases List.mem_map.mp hx with ⟨delta, hdelta, hx⟩ rw [← hx] have hrho := spider_blocked_optionvals_le_rho_le_one (r - (idx + 1)) delta beta hβ have hval := spider_blocked_optionvals_le_val_le_succ delta (idx + 1 - 1) have hxor := spider_blocked_optionvals_le_xor_le_succ (spider_rho (r - (idx + 1)) delta beta) (spider_blocked_val delta (idx + 1 - 1)) hrho omega
The middle singleton option value is at most r.
Simplifying list membership with `List.mem_cons`, `List.not_mem_nil`, and `or_false`, x must be spider_rho 0 beta beta ^^^ spider_blocked_val beta (r - 1). Since beta ≠ free, `spider_rho_zero_same` simplifies spider_rho 0 beta beta to 0, and `Nat.zero_xor` reduces 0 ^^^ v to v. By `spider_blocked_optionvals_le_val_le_succ`, the remaining blocked value is at most (r - 1) + 1, which equals r ≤ r since r ≥ 2 (`omega`).
uses
List.mem_cons,List.not_mem_nil,or_false,spider_rho_zero_same,Nat.zero_xor,spider_blocked_optionvals_le_val_le_succ· simp only [List.mem_cons, List.not_mem_nil, or_false] at hx subst hx rw [spider_rho_zero_same beta hβ, Nat.zero_xor] have := spider_blocked_optionvals_le_val_le_succ beta (r - 1) omega
Each of the trailing two option values is at most r.
Simplifying list membership with `List.mem_cons`, `List.not_mem_nil`, and `or_false`, x is either spider_rho r outward beta or spider_rho_star r beta. In the first case, `spider_blocked_optionvals_le_rho_le_one` shows x ≤ 1, which is at most r by linear arithmetic (`omega`) since r ≥ 2. In the second case, rewriting with `spider_blocked_optionvals_le_rho_star_ne_free` gives x = r ≤ r.
uses
List.mem_cons,List.not_mem_nil,or_false,spider_blocked_optionvals_le_rho_le_one,spider_blocked_optionvals_le_rho_star_ne_free· simp only [List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with rfl | rfl · have := spider_blocked_optionvals_le_rho_le_one r SpiderLegEnd.outward beta hβ omega · rw [spider_blocked_optionvals_le_rho_star_ne_free r beta hβ]
Nat.even_or_odd- Every natural number is either even or odd.
Nat.xor_one_of_even- For any even natural number n, n ^^^ 1 = n + 1.
Nat.xor_one_of_odd- For any odd natural number n, n ^^^ 1 = n - 1.
Nat.xor_comm- Bitwise XOR on natural numbers is commutative: x ^^^ y = y ^^^ x.
spider_blocked_optionvals_le_xor_one_le- For any natural number b, b ^^^ 1 ≤ b + 1.
Nat.mod_lt- For any natural numbers x and y with y > 0, x % y < y.
List.mem_append.mp- If an element is in the concatenation of two lists, it is in the first list or in the second list.
List.mem_flatMap.mp- If an element is in List.flatMap f l, then it is in 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.mem_map.mp- If an element is in List.map f l, then it equals f a for some a in l.
spider_blocked_optionvals_le_rho_le_one- For any height h, leg end delta, and beta ≠ free, spider_rho h delta beta ≤ 1.
spider_blocked_optionvals_le_val_le_succ- For any leg end delta and natural number m, spider_blocked_val delta m ≤ m + 1.
spider_blocked_optionvals_le_xor_le_succ- If a ≤ 1, then a ^^^ b ≤ b + 1 for any natural number b.
List.mem_cons- An element belongs to 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- Disjunction with false is logically equivalent to the proposition itself: (p ∨ False) = p.
spider_rho_zero_same- When φ ≠ free, spider_rho 0 φ φ = 0.
Nat.zero_xor- Bitwise XOR of 0 with x is x: 0 ^^^ x = x.
spider_blocked_optionvals_le_rho_star_ne_free- For any leg end phi ≠ free, spider_rho_star h phi = h.
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_blocked_optionvals_le_xor_one_le (b : ℕ) : b ^^^ 1 ≤ b + 1 := by rcases Nat.even_or_odd b with ⟨k, hk⟩ | ⟨k, hk⟩ · rw [Nat.xor_one_of_even ⟨k, hk⟩] · rw [Nat.xor_one_of_odd ⟨k, hk⟩] omegalemma spider_blocked_optionvals_le_xor_le_succ (a b : ℕ) (ha : a ≤ 1) : a ^^^ b ≤ b + 1 := by interval_cases a · simp · rw [Nat.xor_comm]; exact spider_blocked_optionvals_le_xor_one_le blemma spider_blocked_optionvals_le_rho_le_one (h : ℕ) (delta beta : SpiderLegEnd) (hβ : beta ≠ SpiderLegEnd.free) : spider_rho h delta beta ≤ 1 := by rcases beta with _ | _ | _ · exact absurd rfl hβ · simp only [spider_rho] split_ifs with h1 h2 · have := Nat.mod_lt h (by norm_num : 0 < 2); omega · omega · omega · simp only [spider_rho] split_ifs with h1 h2 · have := Nat.mod_lt h (by norm_num : 0 < 2); omega · omega · omegalemma spider_blocked_optionvals_le_rho_star_ne_free (h : ℕ) (phi : SpiderLegEnd) (hφ : phi ≠ SpiderLegEnd.free) : spider_rho_star h phi = h := by rcases phi with _ | _ | _ <;> simp [spider_rho_star] at *lemma spider_blocked_optionvals_le_val_le_succ (delta : SpiderLegEnd) (m : ℕ) : spider_blocked_val delta m ≤ m + 1 := by rcases delta with _ | _ | _ <;> simp only [spider_blocked_val] <;> split_ifs <;> omega/-- Bound on the options of the blocked two-leg family: all lie in [0, r]. -/theorem spider_blocked_optionvals_le (r : ℕ) (hr : 2 ≤ r) (beta : SpiderLegEnd) (hβ : beta ≠ SpiderLegEnd.free) : ∀ x ∈ spider_blocked_optionvals r beta, x ≤ r := by intro x hx simp only [spider_blocked_optionvals] at hx rcases List.mem_append.mp hx with hx | hx · rcases List.mem_append.mp hx with hx | hx · rcases List.mem_flatMap.mp hx with ⟨idx, hidx, hx⟩ simp only [List.mem_range] at hidx rcases List.mem_map.mp hx with ⟨delta, hdelta, hx⟩ rw [← hx] have hrho := spider_blocked_optionvals_le_rho_le_one (r - (idx + 1)) delta beta hβ have hval := spider_blocked_optionvals_le_val_le_succ delta (idx + 1 - 1) have hxor := spider_blocked_optionvals_le_xor_le_succ (spider_rho (r - (idx + 1)) delta beta) (spider_blocked_val delta (idx + 1 - 1)) hrho omega · simp only [List.mem_cons, List.not_mem_nil, or_false] at hx subst hx rw [spider_rho_zero_same beta hβ, Nat.zero_xor] have := spider_blocked_optionvals_le_val_le_succ beta (r - 1) omega · simp only [List.mem_cons, List.not_mem_nil, or_false] at hx rcases hx with rfl | rfl · have := spider_blocked_optionvals_le_rho_le_one r SpiderLegEnd.outward beta hβ omega · rw [spider_blocked_optionvals_le_rho_star_ne_free r beta hβ]