AFTD Auto-Formalizing Theoretical Domains

spider_none_one_inward_one_outward_opts_mex

theoremverified

For r ≥ 2 and φ ≠ free, the mex of the explicit option list of the κ₁ configuration equals r.

Statement

theorem spider_none_one_inward_one_outward_opts_mex (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
    nat_mex_list (spider_none_one_inward_one_outward_opts r φ) = r
Source
step towards spider_blocked_none_one_inward_one_outward
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

The proof, explained

To determine that the minimum excluded value (mex) of the option list for the $\kappa_1$ spider configuration is $r$, the proof applies the standard characterization of the mex: showing that $r$ does not belong to the list while all natural numbers strictly smaller than $r$ do. These two conditions are supplied directly by two previously established helper lemmas.

  1. The mex of the option list `spider_none_one_inward_one_outward_opts r φ` is $r$.

    The minimum excluded value (mex) of a list is $r$ if $r$ is omitted from the list and every $k < r$ appears in it (`spider_mex_list_eq_of_not_mem_and_lt_mem`). The first requirement is provided by `spider_none_one_inward_one_outward_opts_not_mem`, and the second requirement is provided by `spider_none_one_inward_one_outward_opts_all_lt_mem`.

    lines 3–5

    uses spider_mex_list_eq_of_not_mem_and_lt_mem, spider_none_one_inward_one_outward_opts_not_mem, spider_none_one_inward_one_outward_opts_all_lt_mem

        nat_mex_list (spider_none_one_inward_one_outward_opts r φ) = r := spider_mex_list_eq_of_not_mem_and_lt_mem _ _
        (spider_none_one_inward_one_outward_opts_not_mem r hr φ hφ)
        (spider_none_one_inward_one_outward_opts_all_lt_mem r hr φ hφ)
spider_mex_list_eq_of_not_mem_and_lt_mem
If a natural number $m$ is not in a list $l$, and every natural number $k < m$ is in $l$, then the mex of $l$ is $m$.
spider_none_one_inward_one_outward_opts_not_mem
For $r \ge 2$ and $\phi \neq \text{free}$, the value $r$ is not an element of the option list of the $\kappa_1$ configuration.
spider_none_one_inward_one_outward_opts_all_lt_mem
For $r \ge 2$ and $\phi \neq \text{free}$, every natural number $k < r$ is an element of the option list of the $\kappa_1$ configuration.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The mex of the closed-form option list of the κ₁ family equals r. -/theorem spider_none_one_inward_one_outward_opts_mex (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :    nat_mex_list (spider_none_one_inward_one_outward_opts r φ) = r := spider_mex_list_eq_of_not_mem_and_lt_mem _ _    (spider_none_one_inward_one_outward_opts_not_mem r hr φ hφ)    (spider_none_one_inward_one_outward_opts_all_lt_mem r hr φ hφ)
See it in the graphDiscuss this resultChallenge it