AFTD Auto-Formalizing Theoretical Domains

nat_mex_list_eq_zero

theoremverified

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.

  1. 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`.

    line 3

      by_contra hne
  2. A 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$.

    line 4

    uses nat_mex_list_not_mem_and_lt, Nat.pos_of_ne_zero

      exact 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

/-- 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))
See it in the graphDiscuss this resultChallenge it