AFTD Auto-Formalizing Theoretical Domains

spider_mex_incoming_one_outward_not_mem

theoremverified

The value r ^^^ 1 is not a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.

Statement

theorem spider_mex_incoming_one_outward_not_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    r ^^^ 1 ∉
      ([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 4
  • 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).
  • spider_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 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 proof establishes that the candidate mex value r ^^^ 1 does not belong to the options list of the spider configuration by partitioning the concatenated options list into three parts: an initial 3-element list, an intermediate list flat-mapped over indices i ∈ {1, ..., r - 2}, and a terminal singleton list. For each part, assuming membership yields an equality involving the spider invariant ρ, which is evaluated using the known values of ρ on positive leg lengths (where it takes values in {0, 1}) and on zero length (where it evaluates to 0). In every case, either the injectivity of bitwise XOR with 1 forces r to equal 0, 1, or i ≤ r - 2, or parity-based evaluation of r ^^^ 1 as r ± 1 leads to an immediate arithmetic impossibility, contradicting r ≥ 2.

  1. It suffices to show that r ^^^ 1 does not belong to any of the three concatenated sublists comprising the options list.

    The options list is constructed by concatenating three parts: an initial three-element list, an intermediate family of lists flat-mapped over indices in List.range (r - 2), and a terminal singleton list. Rewriting membership across list concatenation via List.mem_append and distributing negation over disjunction with not_or transforms the goal into proving non-membership in each part separately. The refine tactic splits this into three independent subgoals.

    lines 10–11

    uses List.mem_append, not_or

      simp only [List.mem_append, not_or]
      refine ⟨⟨?_, ?_⟩, ?_⟩
  2. r ^^^ 1 is not an element of the initial three-element list [r, spider_rho (r - 1) inward φ ^^^ 1, spider_rho (r - 1) outward φ ^^^ 1].

    Assume for contradiction that r ^^^ 1 is in this list. Unfolding list membership with List.mem_cons, List.not_mem_nil, and or_false gives three possibilities: r ^^^ 1 = r, or r ^^^ 1 is one of the two ρ-values XORed with 1. Since r ≥ 2, we have 1 ≤ r - 1, so spider_rho_pair_values shows that the pair of inward and outward values of ρ at r - 1 is either (0, 1) or (1, 0). In either case: (1) if r ^^^ 1 = r, case analysis on the parity of r (Nat.even_or_odd) implies r + 1 = r when r is even (Nat.xor_one_of_even) or r - 1 = r when r is odd (Nat.xor_one_of_odd), both impossible; (2) if r ^^^ 1 = 0 ^^^ 1, the injectivity of (· ^^^ 1) from xor_left_involutive implies r = 0, contradicting r ≥ 2; (3) if r ^^^ 1 = 1 ^^^ 1, injectivity implies r = 1, again contradicting r ≥ 2.

    lines 12–33

    uses List.mem_cons, List.not_mem_nil, or_false, spider_rho_pair_values, Nat.even_or_odd, Nat.xor_one_of_even, Nat.xor_one_of_odd, xor_left_involutive

      · intro h
        simp only [List.mem_cons, List.not_mem_nil, or_false] at h
        have hh : 1 ≤ r - 1 := by omega
        rcases spider_rho_pair_values (r - 1) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩
        · rw [h_in, h_out] at h
          rcases h with h1 | h2 | h3
          · rcases Nat.even_or_odd r with he | ho
            · rw [Nat.xor_one_of_even he] at h1; omega
            · rw [Nat.xor_one_of_odd ho] at h1; omega
          · have : r = 0 := (xor_left_involutive 1).injective h2
            omega
          · have : r = 1 := (xor_left_involutive 1).injective h3
            omega
        · rw [h_in, h_out] at h
          rcases h with h1 | h2 | h3
          · rcases Nat.even_or_odd r with he | ho
            · rw [Nat.xor_one_of_even he] at h1; omega
            · rw [Nat.xor_one_of_odd ho] at h1; omega
          · have : r = 1 := (xor_left_involutive 1).injective h2
            omega
          · have : r = 0 := (xor_left_involutive 1).injective h3
            omega
  3. r ^^^ 1 is not an element of the intermediate list obtained by flat-mapping over idx ∈ List.range (r - 2).

    Assume for contradiction that r ^^^ 1 is in the flat-mapped list (List.mem_flatMap). Then there is an index idx < r - 2 (List.mem_range) such that r ^^^ 1 is in the two-element list for i = idx + 1. Since idx < r - 2, we have i ≤ r - 2 and 1 ≤ r - 1 - i. By spider_rho_pair_values, the inward and outward values of ρ at r - 1 - i are {0, 1}. Simplifying with zero_xor, xor_comm, and xor_cancel_right reveals the two list elements to be i ^^^ 1 and i. If r ^^^ 1 = i ^^^ 1, injectivity of XOR (xor_left_involutive) implies r = i, which contradicts i ≤ r - 2 < r. If r ^^^ 1 = i, case analysis on the parity of r (Nat.even_or_odd) gives r + 1 = i (Nat.xor_one_of_even) or r - 1 = i (Nat.xor_one_of_odd), both of which contradict i ≤ r - 2.

    lines 34–56

    uses List.mem_flatMap, List.mem_range, List.mem_cons, List.not_mem_nil, or_false, spider_rho_pair_values, zero_xor, xor_comm, xor_cancel_right, xor_left_involutive, Nat.even_or_odd, Nat.xor_one_of_even, Nat.xor_one_of_odd

      · intro h
        rw [List.mem_flatMap] at h
        rcases h with ⟨idx, hidx, hmem⟩
        rw [List.mem_range] at hidx
        simp only [List.mem_cons, List.not_mem_nil, or_false] at hmem
        let i := idx + 1
        have hi : i ≤ r - 2 := by omega
        have hh : 1 ≤ r - 1 - i := by omega
        rcases spider_rho_pair_values (r - 1 - i) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩
        · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem
          rcases hmem with h1 | h2
          · have : r = i := (xor_left_involutive 1).injective h1
            omega
          · rcases Nat.even_or_odd r with he | ho
            · rw [Nat.xor_one_of_even he] at h2; omega
            · rw [Nat.xor_one_of_odd ho] at h2; omega
        · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem
          rcases hmem with h1 | h2
          · rcases Nat.even_or_odd r with he | ho
            · rw [Nat.xor_one_of_even he] at h1; omega
            · rw [Nat.xor_one_of_odd ho] at h1; omega
          · have : r = i := (xor_left_involutive 1).injective h2
            omega
  4. r ^^^ 1 is not an element of the singleton list [spider_rho 0 φ φ ^^^ ((r - 1) ^^^ 1)].

    Assume for contradiction that r ^^^ 1 is in the singleton list (List.mem_singleton). Because φ ≠ free, spider_rho_zero_same gives ρ(0, φ, φ) = 0, so the list element simplifies via zero_xor to (r - 1) ^^^ 1. The equation r ^^^ 1 = (r - 1) ^^^ 1 implies r = r - 1 by injectivity of XOR (xor_left_involutive). Linear arithmetic (omega) derives a contradiction from r = r - 1, completing the proof.

    lines 57–61

    uses List.mem_singleton, spider_rho_zero_same, zero_xor, xor_left_involutive

      · intro h
        simp only [List.mem_singleton] at h
        rw [spider_rho_zero_same φ hφ, zero_xor] at h
        have : r = r - 1 := (xor_left_involutive 1).injective h
        omega
List.mem_append
An element belongs to the concatenation of two lists if and only if it belongs to the first list or the second list.
not_or
The negation of a disjunction is equivalent to the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
List.mem_cons
An element belongs to a prepended list 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
A proposition disjoined with False is equivalent to the proposition itself: (p ∨ False) ↔ p.
spider_rho_pair_values
For any leg length h ≥ 1 and non-free end-condition φ, the pair of values (ρ(h, inward, φ), ρ(h, outward, φ)) is either (0, 1) or (1, 0).
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.
Nat.xor_one_of_odd
For an odd natural number n, n ^^^ 1 = n - 1.
xor_left_involutive
Bitwise XOR with a fixed value is an involution, and in particular is an injective function.
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.
zero_xor
Bitwise XOR of 0 with any element a is equal to a (0 ^^^ a = a).
xor_comm
Bitwise XOR is commutative: a ^^^ b = b ^^^ a.
xor_cancel_right
Bitwise XOR with the same value twice cancels out: (a ^^^ b) ^^^ b = a.
List.mem_singleton
An element belongs to the singleton list [b] if and only if it equals b.
spider_rho_zero_same
For length 0 and identical non-free leg end conditions φ, ρ(0, φ, φ) = 0.

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

/-- The candidate mex value r ^^^ 1 is not an element of the options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}). -/theorem spider_mex_incoming_one_outward_not_mem (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    r ^^^ 1 ∉      ([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  simp only [List.mem_append, not_or]  refine ⟨⟨?_, ?_⟩, ?_⟩  · intro h    simp only [List.mem_cons, List.not_mem_nil, or_false] at h    have hh : 1 ≤ r - 1 := by omega    rcases spider_rho_pair_values (r - 1) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩    · rw [h_in, h_out] at h      rcases h with h1 | h2 | h3      · rcases Nat.even_or_odd r with he | ho        · rw [Nat.xor_one_of_even he] at h1; omega        · rw [Nat.xor_one_of_odd ho] at h1; omega      · have : r = 0 := (xor_left_involutive 1).injective h2        omega      · have : r = 1 := (xor_left_involutive 1).injective h3        omega    · rw [h_in, h_out] at h      rcases h with h1 | h2 | h3      · rcases Nat.even_or_odd r with he | ho        · rw [Nat.xor_one_of_even he] at h1; omega        · rw [Nat.xor_one_of_odd ho] at h1; omega      · have : r = 1 := (xor_left_involutive 1).injective h2        omega      · have : r = 0 := (xor_left_involutive 1).injective h3        omega  · intro h    rw [List.mem_flatMap] at h    rcases h with ⟨idx, hidx, hmem⟩    rw [List.mem_range] at hidx    simp only [List.mem_cons, List.not_mem_nil, or_false] at hmem    let i := idx + 1    have hi : i ≤ r - 2 := by omega    have hh : 1 ≤ r - 1 - i := by omega    rcases spider_rho_pair_values (r - 1 - i) hh φ hφ with ⟨h_in, h_out⟩ | ⟨h_in, h_out⟩    · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem      rcases hmem with h1 | h2      · have : r = i := (xor_left_involutive 1).injective h1        omega      · rcases Nat.even_or_odd r with he | ho        · rw [Nat.xor_one_of_even he] at h2; omega        · rw [Nat.xor_one_of_odd ho] at h2; omega    · rw [h_in, h_out, zero_xor, xor_comm 1 (i ^^^ 1), xor_cancel_right] at hmem      rcases hmem with h1 | h2      · rcases Nat.even_or_odd r with he | ho        · rw [Nat.xor_one_of_even he] at h1; omega        · rw [Nat.xor_one_of_odd ho] at h1; omega      · have : r = i := (xor_left_involutive 1).injective h2        omega  · intro h    simp only [List.mem_singleton] at h    rw [spider_rho_zero_same φ hφ, zero_xor] at h    have : r = r - 1 := (xor_left_involutive 1).injective h    omega
See it in the graphDiscuss this resultChallenge it