AFTD Auto-Formalizing Theoretical Domains

spider_none_one_inward_one_outward_opts_all_lt_mem

theoremverified

For r ≥ 2 and φ ≠ free, every k < r is a member of the closed-form option list of the κ₁ family.

Statement

theorem spider_none_one_inward_one_outward_opts_all_lt_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    ∀ k < r, k ∈ 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

The proof, explained

The theorem states that every natural number k < r belongs to the options list spider_none_one_inward_one_outward_opts r φ when r ≥ 2 and φ ≠ free. The proof unfolds the definition of the options list and applies spider_rho_pair_values, which guarantees that at any positive height, exactly one of the inward and outward leg rho values is 0 and the other is 1. Membership is then established by case analysis on k: numbers k < 2 correspond to the explicit values 0 and 1 in the initial segment; k = r - 1 matches the trailing element of the list; and for intermediate values 2 ≤ k ≤ r - 2, choosing index a = k - 1 produces an option where the zero rho value yields 0 ^^^ (a + 1) = k.

  1. Fix k < r and note that r - 1 ≥ 1.

    We introduce an arbitrary natural number k satisfying k < r. Because r ≥ 2, linear arithmetic (via omega) gives r - 1 ≥ 1.

    lines 4–5

      intro k hk
      have hr1 : 1 ≤ r - 1 := by omega
  2. Expanding the definition of the options list reduces membership to showing k is an explicit initial element (0, 1, or r ^^^ 1), matches the trailing element r - 1, or is produced by the intermediate flatMap range.

    Applying spider_rho_pair_values at height r - 1 shows that one of the inward and outward values of spider_rho is 0 and the other is 1. Unfolding spider_none_one_inward_one_outward_opts and simplifying list membership via List.mem_append, List.mem_cons, List.mem_flatMap, List.mem_range, List.not_mem_nil, and or_false reduces the goal in both parity branches to a disjunction over the elements of the options list.

    lines 6–9

    uses spider_rho_pair_values, List.mem_append, List.mem_cons, List.mem_flatMap, List.mem_range, List.not_mem_nil, or_false

      rcases spider_rho_pair_values (r - 1) hr1 φ hφ with ⟨h0, h1⟩ | ⟨h1, h0⟩ <;>
        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, or_false, h0, h1]
  3. In the first parity case (inward rho is 0, outward rho is 1), membership holds when k < 2.

    Using Nat.lt_or_ge, we split into cases k < 2 and k ≥ 2. When k < 2, k is either 0 or 1 (interval_cases). Since both 0 and 1 are present in the options list, simp closes each subcase by reflexivity.

    lines 10–11

    uses Nat.lt_or_ge

      · rcases Nat.lt_or_ge k 2 with hlt2 | hge2
        · interval_cases k <;> simp
  4. When k ≥ 2 and k = r - 1, membership holds via the final element of the list.

    We split on whether k = r - 1. When it is, k directly matches the final singleton [r - 1] in the options list, closing the goal with Or.inr.

    lines 12–13

    uses Or.inr

        · by_cases hkr : k = r - 1
          · exact Or.inr hkr
  5. When 2 ≤ k ≤ r - 2, k is obtained from the flatMap segment at index a = k - 1.

    Since k < r and k ≠ r - 1, we have k ≤ r - 2 and therefore r - 1 - k ≥ 1. By spider_rho_pair_values at height r - 1 - k, one of the two leg orientations has rho value 0. Choosing index a = k - 1 < r - 2, the remaining height is r - 2 - a = r - 1 - k. Selecting the leg orientation whose rho is 0, the option value evaluates to 0 ^^^ (a + 1) = (k - 1) + 1 = k by Nat.zero_xor and linear arithmetic.

    lines 14–21

    uses spider_rho_pair_values, Or.inl, Or.inr, Nat.zero_xor

          · have hle : k ≤ r - 2 := by omega
            rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩
            · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩)
              have harg : r - 2 - (k - 1) = r - 1 - k := by omega
              rw [harg, g0, Nat.zero_xor]; omega
            · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩)
              have harg : r - 2 - (k - 1) = r - 1 - k := by omega
              rw [harg, g0, Nat.zero_xor]; omega
  6. In the second parity case (inward rho is 1, outward rho is 0), membership holds when k < 2.

    As in the first case, case splitting with Nat.lt_or_ge leaves k = 0 and k = 1, both of which appear in the options list and are discharged by interval_cases and simp.

    lines 22–23

    uses Nat.lt_or_ge

      · rcases Nat.lt_or_ge k 2 with hlt2 | hge2
        · interval_cases k <;> simp
  7. When k ≥ 2 and k = r - 1, membership holds via the final element of the list.

    If k = r - 1, k matches the trailing element [r - 1] of the options list, closing the goal via Or.inr.

    lines 24–25

    uses Or.inr

        · by_cases hkr : k = r - 1
          · exact Or.inr hkr
  8. When 2 ≤ k ≤ r - 2, k is obtained from the flatMap segment at index a = k - 1.

    Just as in the first parity branch, k ≤ r - 2 implies r - 1 - k ≥ 1. Applying spider_rho_pair_values at height r - 1 - k and picking index a = k - 1 < r - 2, the branch with rho = 0 simplifies via Nat.zero_xor to 0 ^^^ (a + 1) = k.

    lines 26–33

    uses spider_rho_pair_values, Or.inl, Or.inr, Nat.zero_xor

          · have hle : k ≤ r - 2 := by omega
            rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩
            · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩)
              have harg : r - 2 - (k - 1) = r - 1 - k := by omega
              rw [harg, g0, Nat.zero_xor]; omega
            · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩)
              have harg : r - 2 - (k - 1) = r - 1 - k := by omega
              rw [harg, g0, Nat.zero_xor]; omega
spider_rho_pair_values
For any height h ≥ 1 and any non-free leg end φ, exactly one of the inward and outward leg values of spider_rho is 0 and the other is 1.
List.mem_append
An element belongs to the concatenation of two lists s ++ t if and only if it belongs to s or to t.
List.mem_cons
An element a belongs to b :: l if and only if a = b or a ∈ l.
List.mem_flatMap
An element b belongs to flatMap f l if and only if there is an element a ∈ l such that b ∈ f a.
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 [].
or_false
For any proposition p, (p ∨ False) is logically equivalent to p.
Nat.lt_or_ge
For any natural numbers n and m, either n < m or n ≥ m.
Or.inr
If b holds, then the disjunction a ∨ b holds (right injection).
Or.inl
If a holds, then the disjunction a ∨ b holds (left injection).
Nat.zero_xor
Zero is the identity element for bitwise XOR on natural numbers: 0 ^^^ x = x.

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 below r occurs in the closed-form option list. -/theorem spider_none_one_inward_one_outward_opts_all_lt_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    ∀ k < r, k ∈ spider_none_one_inward_one_outward_opts r φ := by  intro k hk  have hr1 : 1 ≤ r - 1 := by omega  rcases spider_rho_pair_values (r - 1) hr1 φ hφ with ⟨h0, h1⟩ | ⟨h1, h0⟩ <;>    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, or_false, h0, h1]  · rcases Nat.lt_or_ge k 2 with hlt2 | hge2    · interval_cases k <;> simp    · by_cases hkr : k = r - 1      · exact Or.inr hkr      · have hle : k ≤ r - 2 := by omega        rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩        · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩)          have harg : r - 2 - (k - 1) = r - 1 - k := by omega          rw [harg, g0, Nat.zero_xor]; omega        · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩)          have harg : r - 2 - (k - 1) = r - 1 - k := by omega          rw [harg, g0, Nat.zero_xor]; omega  · rcases Nat.lt_or_ge k 2 with hlt2 | hge2    · interval_cases k <;> simp    · by_cases hkr : k = r - 1      · exact Or.inr hkr      · have hle : k ≤ r - 2 := by omega        rcases spider_rho_pair_values (r - 1 - k) (by omega) φ hφ with ⟨g0, g1⟩ | ⟨g1, g0⟩        · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inl ?_⟩)          have harg : r - 2 - (k - 1) = r - 1 - k := by omega          rw [harg, g0, Nat.zero_xor]; omega        · refine Or.inl (Or.inr ⟨k - 1, by omega, Or.inr ?_⟩)          have harg : r - 2 - (k - 1) = r - 1 - k := by omega          rw [harg, g0, Nat.zero_xor]; omega
See it in the graphDiscuss this resultChallenge it