AFTD Auto-Formalizing Theoretical Domains

spider_blocked_optionvals_le

theoremverified

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.

  1. 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`).

    lines 1–5

    uses Nat.even_or_odd, Nat.xor_one_of_even, Nat.xor_one_of_odd

    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⟩]
        omega
  2. 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`.

    lines 7–10

    uses Nat.xor_comm, spider_blocked_optionvals_le_xor_one_le

    lemma 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
  3. 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.

    lines 12–25

    uses Nat.mod_lt

    lemma 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
  4. 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.

    lines 27–29

    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 *
  5. 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`).

    lines 31–33

    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
  6. 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`.

    lines 36–40

    uses List.mem_append.mp

    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
  7. 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.

    lines 41–50

    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
  8. 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`).

    lines 51–55

    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
  9. 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.

    lines 56–60

    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

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β]
See it in the graphDiscuss this resultChallenge it