AFTD Auto-Formalizing Theoretical Domains

nat_mex_list_eq_one

theoremverified

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.

  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).

    line 3

    uses nat_mex_list_not_mem_and_lt

      obtain ⟨hnot, hlt⟩ := nat_mex_list_not_mem_and_lt l
  2. nat_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.

    lines 4–8

      have h_ne_zero : nat_mex_list l ≠ 0 := by
        intro h
        apply hnot
        rw [h]
        exact h0
  3. 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.

    lines 9–12

      have h_le_one : nat_mex_list l ≤ 1 := by
        by_contra! h2
        have : 1 ∈ l := hlt 1 h2
        exact h1 this
  4. 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.

    line 13

      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

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