AFTD Auto-Formalizing Theoretical Domains

spider_mex_incoming_one_outward_all_lt_mem

theoremverified

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

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

    lines 11–16

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

    lines 18–23

    uses spider_rho_pair_values

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

    lines 25–36

    uses List.mem_flatMap, List.mem_range, spider_rho_pair_values, zero_xor, xor_comm, xor_cancel_right

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

    lines 38–49

    uses List.mem_flatMap, List.mem_range, spider_rho_pair_values, zero_xor, xor_comm, xor_cancel_right

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

    lines 51–52

      intro k hk
      change k ∈ L_head ++ L_flat ++ L_tail
  6. 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`.

    lines 53–72

    uses Nat.even_or_odd, Nat.xor_one_of_even, lt_or_ge, eq_or_lt_of_le

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

    lines 73–79

    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.

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

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