nat_mex_list_eq_one
If a list of naturals contains 0 but not 1, then its mex is 1.
Statement
theorem nat_mex_list_eq_one (l : List ℕ) (h0 : 0 ∈ l) (h1 : 1 ∉ l) : nat_mex_list l = 1- Source
- step towards spider_grundy_val_one_two
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- Used by 3
- spider_mex_two_leg_one_freeGiven an explicit options list where every element has parity k % 2, the minimum excluded value is 1 - k % 2 (which is 1 when k is even,…
- spider_mex_one_twoThe mex of the explicit closed-form option list of S(1,2,z) (8 head values plus the long block, after substituting all closed forms)…
- nat_mex_list_eq_of_all_eq_bitFor any list of natural numbers whose elements all equal a single bit b ∈ {0, 1}, if the list is non-empty, its nat_mex_list is 1 - b.
The proof, explained
The proof characterises the mex of l by its defining properties: it is not in l, but every strictly smaller natural number is in l. Because 0 is in l, the mex cannot be 0, and because 1 is not in l, the mex cannot be strictly greater than 1. Since the only natural number at most 1 other than 0 is 1, the mex must be 1.
The mex of l is not in l, and every natural number strictly less than the mex belongs to l.
We unpack the defining properties of the minimum excluded natural number for l using nat_mex_list_not_mem_and_lt: nat_mex_list l does not belong to l (hnot), and any k < nat_mex_list l must belong to l (hlt).
uses
nat_mex_list_not_mem_and_ltobtain ⟨hnot, hlt⟩ := nat_mex_list_not_mem_and_lt lnat_mex_list l ≠ 0
Suppose for contradiction that the mex were 0. Then, by the non-membership property, 0 would not be in l, which contradicts the hypothesis h0 that 0 ∈ l.
have h_ne_zero : nat_mex_list l ≠ 0 := by intro h apply hnot rw [h] exact h0
nat_mex_list l ≤ 1
Suppose for contradiction that nat_mex_list l > 1. Then 1 < nat_mex_list l, which by the minimality property implies that 1 ∈ l. This contradicts the assumption h1 that 1 ∉ l.
have h_le_one : nat_mex_list l ≤ 1 := by by_contra! h2 have : 1 ∈ l := hlt 1 h2 exact h1 this
nat_mex_list l = 1
Since nat_mex_list l is a natural number such that nat_mex_list l ≠ 0 and nat_mex_list l ≤ 1, linear integer arithmetic determines that it must equal 1.
omega
nat_mex_list_not_mem_and_lt- The mex of a list of naturals is not in the list, and any natural strictly less than the mex is in the list.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The mex of a list containing 0 but not 1 is 1. -/theorem nat_mex_list_eq_one (l : List ℕ) (h0 : 0 ∈ l) (h1 : 1 ∉ l) : nat_mex_list l = 1 := by obtain ⟨hnot, hlt⟩ := nat_mex_list_not_mem_and_lt l have h_ne_zero : nat_mex_list l ≠ 0 := by intro h apply hnot rw [h] exact h0 have h_le_one : nat_mex_list l ≤ 1 := by by_contra! h2 have : 1 ∈ l := hlt 1 h2 exact h1 this omega