nat_mex_list_eq_zero
If a list of naturals does not contain 0, then its mex (minimum excluded value) is 0.
Statement
theorem nat_mex_list_eq_zero (l : List ℕ) (h : 0 ∉ l) : nat_mex_list l = 0- 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 theorem is proved by contradiction. If the mex of the list were non-zero, it would be strictly positive. By the defining property of the minimum excluded value, every natural number strictly less than the mex must belong to the list, which implies that 0 is in the list, contradicting the hypothesis that 0 is not in the list.
Assume, for contradiction, that the mex of the list is not 0.
We proceed by contradiction (`by_contra hne`), assuming that `nat_mex_list l ≠ 0`.
by_contra hneA contradiction is reached, because 0 must belong to the list.
Because the mex is non-zero, it is strictly positive (`Nat.pos_of_ne_zero`), which means $0 < \\operatorname{nat\\_mex\\_list} l$. By the second part of `nat_mex_list_not_mem_and_lt`, any natural number strictly less than the mex must be in the list $l$. Applying this to $0$ shows that $0 \\in l$, directly contradicting the hypothesis $h : 0 \\notin l$.
uses
nat_mex_list_not_mem_and_lt,Nat.pos_of_ne_zeroexact h ((nat_mex_list_not_mem_and_lt l).2 0 (Nat.pos_of_ne_zero hne))
Nat.pos_of_ne_zero- If a natural number is not zero, then it is strictly greater than zero.
nat_mex_list_not_mem_and_lt- The mex of a list of natural numbers is not in the list, and every natural number strictly less than the mex is an element of 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 not containing 0 is 0. -/theorem nat_mex_list_eq_zero (l : List ℕ) (h : 0 ∉ l) : nat_mex_list l = 0 := by by_contra hne exact h ((nat_mex_list_not_mem_and_lt l).2 0 (Nat.pos_of_ne_zero hne))