AFTD Auto-Formalizing Theoretical Domains

spider_none_one_inward_one_outward_opts_not_mem

theoremverified

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

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.

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

    lines 3–6

    uses congrArg, Nat.testBit_xor

      intro h
      have h2 := congrArg (fun n => n.testBit 0) h
      simp only [Nat.testBit_xor] at h2
      simp at h2
  2. 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.

    lines 13–15

    uses spider_rho_pair_values

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

    lines 20–25

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

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

    lines 30–33

    uses List.mem_append, List.mem_cons, List.mem_flatMap, List.mem_range, List.not_mem_nil, List.cons_append, List.nil_append

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

    lines 34–35

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

    lines 36–41

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

    lines 42–51

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

    lines 52–54

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

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

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