AFTD Auto-Formalizing Theoretical Domains

spider_mex_incoming_one_outward

theoremverified

The minimum excluded value of the explicit options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2 and φ ≠ free.

Statement

theorem spider_mex_incoming_one_outward (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    nat_mex_list
      ([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)]) = r ^^^ 1
Source
step towards spider_blocked_incoming_one_outward
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • nat_mex_list_not_mem_and_ltFor a list l of naturals, nat_mex_list l is not a member of l, and every natural number below nat_mex_list l is a member of l.
  • spider_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 0.
  • 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_mex_incoming_one_outward_not_memThe value r ^^^ 1 is not a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.
  • spider_mex_incoming_one_outward_all_lt_memEvery natural number k < r ^^^ 1 is a member of the explicit options list for (in;{(1,outward),(r,φ)}) when r ≥ 2 and φ ≠ free.
  • 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…
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
  • 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

The proof, explained

The proof determines the minimum excluded value (mex) of the option list by applying a general characterization lemma: if a candidate value does not appear in a list and all strictly smaller numbers do, then that value is the mex. The proof first establishes this criterion by trichotomy against the definition of mex, then applies two dedicated lemmas showing that r ^^^ 1 satisfies both conditions for the options list.

  1. For any list l and natural number m, if m ∉ l and all k < m are in l, then the mex of l is m.

    The characterizing property of the mex gives that nat_mex_list l ∉ l and all k < nat_mex_list l are in l. Applying trichotomy to nat_mex_list l and m rules out both strict inequalities: if nat_mex_list l < m, then nat_mex_list l ∈ l by the assumption on m, contradiction; if m < nat_mex_list l, then m ∈ l by the property of mex, contradicting m ∉ l. Hence nat_mex_list l = m.

    lines 3–7

    uses nat_mex_list_not_mem_and_lt, lt_trichotomy

      have ⟨h1, h2⟩ := nat_mex_list_not_mem_and_lt l
      rcases lt_trichotomy (nat_mex_list l) m with hlt | heq | hgt
      · exact (h1 (h_all_lt (nat_mex_list l) hlt)).elim
      · exact heq
      · exact (h_not_mem (h2 m hgt)).elim
  2. It suffices to show that r ^^^ 1 is not in the options list and that every k < r ^^^ 1 is in the list.

    Applying the general mex characterization lemma spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem reduces the evaluation of the mex to verifying non-membership of r ^^^ 1 and membership of all smaller natural numbers.

    line 18

    uses spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem

      apply spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem
  3. The value r ^^^ 1 is not in the options list.

    This is established by the lemma spider_mex_incoming_one_outward_not_mem.

    line 19

    uses spider_mex_incoming_one_outward_not_mem

      · exact spider_mex_incoming_one_outward_not_mem r hr φ hφ
  4. Every natural number k < r ^^^ 1 belongs to the options list.

    This is established by the lemma spider_mex_incoming_one_outward_all_lt_mem, completing the proof.

    line 20

    uses spider_mex_incoming_one_outward_all_lt_mem

      · exact spider_mex_incoming_one_outward_all_lt_mem r hr φ hφ
nat_mex_list_not_mem_and_lt
For any list of natural numbers, its mex does not belong to the list, and every strictly smaller natural number belongs to the list.
lt_trichotomy
For any two elements a and b in a linear order, exactly one of a < b, a = b, or b < a holds.
spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem
If a natural number m is not in a list l and every k < m is in l, then the mex of l is m.
spider_mex_incoming_one_outward_not_mem
The value r ^^^ 1 does not belong to the explicit option list of the spider configuration.
spider_mex_incoming_one_outward_all_lt_mem
Every natural number strictly smaller than r ^^^ 1 belongs to the explicit option list of the spider configuration.

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_mex_incoming_one_outward_of_not_mem_and_all_lt_mem (l : List ℕ) (m : ℕ)    (h_not_mem : m ∉ l) (h_all_lt : ∀ k < m, k ∈ l) : nat_mex_list l = m := by  have ⟨h1, h2⟩ := nat_mex_list_not_mem_and_lt l  rcases lt_trichotomy (nat_mex_list l) m with hlt | heq | hgt  · exact (h1 (h_all_lt (nat_mex_list l) hlt)).elim  · exact heq  · exact (h_not_mem (h2 m hgt)).elim/-- The mex of the explicit closed-form option list of the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2 and φ ≠ free. -/theorem spider_mex_incoming_one_outward (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    nat_mex_list      ([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)]) = r ^^^ 1 := by  apply spider_mex_incoming_one_outward_of_not_mem_and_all_lt_mem  · exact spider_mex_incoming_one_outward_not_mem r hr φ hφ  · exact spider_mex_incoming_one_outward_all_lt_mem r hr φ hφ
See it in the graphDiscuss this resultChallenge it