AFTD Auto-Formalizing Theoretical Domains

nat_mex_list_not_mem_and_lt

theoremverified

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

Statement

theorem nat_mex_list_not_mem_and_lt (l : List ℕ) :
    nat_mex_list l ∉ l ∧ ∀ k, k < nat_mex_list l → k ∈ l
Source
step towards spider_eventual_parity_two_three
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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 7

The proof, explained

The theorem proves that `nat_mex_list l`—computed by a loop starting at 0 with fuel |l| + 1—is the minimum excluded value of l. An auxiliary lemma shows by induction on fuel that searching from n either finds an excluded value not in l whose predecessors down to n are all in l, or exhausts fuel reaching n + fuel with all intermediate values in l. When specialized to start 0 with fuel |l| + 1, the exhausted-fuel alternative would imply that all |l| + 1 distinct elements of `List.range (l.length + 1)` belong to l, contradicting the list length |l|. Hence only the first alternative can occur, proving that `nat_mex_list l ∉ l` and all smaller naturals belong to l.

  1. When fuel is 0, the loop specification holds because the loop reaches n + 0 with no intermediate values to check.

    We proceed by induction on `fuel`, generalizing over n. For the base case `fuel = 0`, the loop immediately returns n, which equals n + 0. The second disjunct holds: the equality is definitional, and the condition that every k with n ≤ k < n + 0 belongs to l is vacuously satisfied because n ≤ k < n is an arithmetic contradiction.

    lines 4–7

      induction fuel generalizing n with
      | zero =>
        right
        exact ⟨rfl, fun k h1 h2 => by omega⟩
  2. For fuel + 1, we unfold one step of the loop and branch on whether n ∈ l.

    In the inductive step, the definition of the loop unwinds one iteration: if n ∈ l, it recurses to `loop l (n + 1) fuel`, and otherwise it terminates with n. We rewrite using this definition and perform a case split on whether n ∈ l.

    lines 8–11

      | succ fuel ih =>
        have hstep : nat_mex_list.loop l n (fuel + 1) = if n ∈ l then nat_mex_list.loop l (n + 1) fuel else n := rfl
        rw [hstep]
        by_cases hn : n ∈ l
  3. If n ∈ l and the induction hypothesis on n + 1 yields an excluded value, then the first disjunct holds for n.

    Since n ∈ l, rewriting with `if_pos` shows the loop proceeds to `loop l (n + 1) fuel`. In the first case of the induction hypothesis for n + 1, the loop produces a value m ∉ l such that every k with n + 1 ≤ k < m is in l. For any k with n ≤ k < m, by `eq_or_lt_of_le` either k = n (which is in l by assumption) or n < k (which implies n + 1 ≤ k < m, so k ∈ l by the induction hypothesis). Thus the first disjunct holds for n.

    lines 12–18

    uses if_pos, eq_or_lt_of_le

        · rw [if_pos hn]
          rcases ih (n + 1) with (⟨h1, h2⟩ | ⟨h1, h2⟩)
          · left
            refine ⟨h1, fun k hk1 hk2 => ?_⟩
            rcases eq_or_lt_of_le hk1 with rfl | hlt
            · exact hn
            · exact h2 k hlt hk2
  4. If n ∈ l and the induction hypothesis on n + 1 exhausts fuel, then the second disjunct holds for n.

    In the second case of the induction hypothesis for n + 1, the loop reaches (n + 1) + fuel = n + (fuel + 1) with all k in [n + 1, n + 1 + fuel) belonging to l. For any k with n ≤ k < n + (fuel + 1), either k = n (in l by assumption) or n < k (so n + 1 ≤ k < n + 1 + fuel, hence in l by the induction hypothesis), using `eq_or_lt_of_le` and linear arithmetic.

    lines 19–23

    uses eq_or_lt_of_le

          · right
            refine ⟨by omega, fun k hk1 hk2 => ?_⟩
            rcases eq_or_lt_of_le hk1 with rfl | hlt
            · exact hn
            · exact h2 k hlt (by omega)
  5. If n ∉ l, the loop halts immediately and the first disjunct holds.

    Since n ∉ l, rewriting with `if_neg` shows that the loop returns n. The first disjunct holds: n ∉ l is our hypothesis, and the condition on all k with n ≤ k < n is vacuously true by linear arithmetic.

    lines 24–26

    uses if_neg

        · rw [if_neg hn]
          left
          exact ⟨hn, fun k hk1 hk2 => by omega⟩
  6. Expressing `nat_mex_list l` via the loop specification with start 0 and fuel |l| + 1, the theorem follows if an excluded value is found.

    By definition, `nat_mex_list l` is `loop l 0 (l.length + 1)`. Applying `nat_mex_list_not_mem_and_lt_loop_spec` with starting value 0 and fuel l.length + 1, the first alternative gives that the returned value is not in l and every k with 0 ≤ k < loop is in l. Since 0 ≤ k is unconditionally true for naturals (`Nat.zero_le`), every k smaller than the loop's output belongs to l, which directly establishes the theorem.

    lines 31–33

    uses nat_mex_list_not_mem_and_lt_loop_spec, Nat.zero_le

      change (nat_mex_list.loop l 0 (l.length + 1) ∉ l ∧ ∀ k, k < nat_mex_list.loop l 0 (l.length + 1) → k ∈ l)
      rcases nat_mex_list_not_mem_and_lt_loop_spec l (l.length + 1) 0 with (⟨h1, h2⟩ | ⟨-, h2⟩)
      · exact ⟨h1, fun k hk => h2 k (Nat.zero_le k) hk⟩
  7. If the loop instead exhausts its fuel, then every element of `List.range (l.length + 1)` belongs to l.

    Under the second alternative of the loop specification, every natural k < l.length + 1 (with 0 ≤ k by `Nat.zero_le`) must belong to l. Any element x in `List.range (l.length + 1)` satisfies x < l.length + 1 by `List.mem_range`, so x ∈ l. Thus `List.range (l.length + 1) ⊆ l`.

    lines 34–37

    uses Nat.zero_le, List.mem_range

      · have hsub : List.range (l.length + 1) ⊆ l := by
          intro x hx
          rw [List.mem_range] at hx
          exact h2 x (Nat.zero_le x) (by omega)
  8. The inclusion `List.range (l.length + 1) ⊆ l` yields a length contradiction, ruling out the exhausted-fuel case.

    Because `List.range (l.length + 1)` contains no duplicate elements (`List.nodup_range`), its inclusion in l implies that its length is at most that of l (`List.Nodup.length_le_of_subset`). Since the length of `List.range (l.length + 1)` is l.length + 1 (`List.length_range`), we obtain l.length + 1 ≤ l.length, an impossible inequality that `omega` uses to complete the proof by contradiction.

    lines 38–40

    uses List.Nodup.length_le_of_subset, List.nodup_range, List.length_range

        have hle := List.Nodup.length_le_of_subset List.nodup_range hsub
        rw [List.length_range] at hle
        omega
if_pos
If condition c is true, then `if c then t else e` equals t.
eq_or_lt_of_le
If a ≤ b in a partial order, then either a = b or a < b.
if_neg
If condition c is false, then `if c then t else e` equals e.
nat_mex_list_not_mem_and_lt_loop_spec
For any list l, starting number n, and fuel, the loop either finds an excluded value not in l whose predecessors down to n belong to l, or reaches n + fuel with all intermediate values in l.
Nat.zero_le
Every natural number is greater than or equal to 0.
List.mem_range
A natural number m is an element of `List.range n` if and only if m < n.
List.Nodup.length_le_of_subset
If a duplicate-free list l₁ is a subset of l₂, then the length of l₁ is at most the length of l₂.
List.nodup_range
The list `List.range n` has no duplicate elements.
List.length_range
The length of `List.range n` is n.

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

lemma nat_mex_list_not_mem_and_lt_loop_spec (l : List ℕ) (fuel : ℕ) (n : ℕ) :    (nat_mex_list.loop l n fuel ∉ l ∧ (∀ k, n ≤ k → k < nat_mex_list.loop l n fuel → k ∈ l)) ∨    (nat_mex_list.loop l n fuel = n + fuel ∧ (∀ k, n ≤ k → k < n + fuel → k ∈ l)) := by  induction fuel generalizing n with  | zero =>    right    exact ⟨rfl, fun k h1 h2 => by omega⟩  | succ fuel ih =>    have hstep : nat_mex_list.loop l n (fuel + 1) = if n ∈ l then nat_mex_list.loop l (n + 1) fuel else n := rfl    rw [hstep]    by_cases hn : n ∈ l    · rw [if_pos hn]      rcases ih (n + 1) with (⟨h1, h2⟩ | ⟨h1, h2⟩)      · left        refine ⟨h1, fun k hk1 hk2 => ?_⟩        rcases eq_or_lt_of_le hk1 with rfl | hlt        · exact hn        · exact h2 k hlt hk2      · right        refine ⟨by omega, fun k hk1 hk2 => ?_⟩        rcases eq_or_lt_of_le hk1 with rfl | hlt        · exact hn        · exact h2 k hlt (by omega)    · rw [if_neg hn]      left      exact ⟨hn, fun k hk1 hk2 => by omega⟩/-- The mex of a finite list of naturals is absent from the list, and every smaller number occurs in it. -/theorem nat_mex_list_not_mem_and_lt (l : List ℕ) :    nat_mex_list l ∉ l ∧ ∀ k, k < nat_mex_list l → k ∈ l := by  change (nat_mex_list.loop l 0 (l.length + 1) ∉ l ∧ ∀ k, k < nat_mex_list.loop l 0 (l.length + 1) → k ∈ l)  rcases nat_mex_list_not_mem_and_lt_loop_spec l (l.length + 1) 0 with (⟨h1, h2⟩ | ⟨-, h2⟩)  · exact ⟨h1, fun k hk => h2 k (Nat.zero_le k) hk⟩  · have hsub : List.range (l.length + 1) ⊆ l := by      intro x hx      rw [List.mem_range] at hx      exact h2 x (Nat.zero_le x) (by omega)    have hle := List.Nodup.length_le_of_subset List.nodup_range hsub    rw [List.length_range] at hle    omega
See it in the graphDiscuss this resultChallenge it