nat_mex_list_not_mem_and_lt
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
- spider_none_one_inward_one_outward_opts_mexFor r ≥ 2 and φ ≠ free, the mex of the explicit option list of the κ₁ configuration equals r.
- spider_mex_incoming_one_outwardThe minimum excluded value of the explicit options list for the configuration κ₂ = (in;{(1,outward),(r,φ)}) equals r ^^^ 1 for every r ≥ 2…
- 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_oneIf a list of naturals contains 0 but not 1, then its mex is 1.
- nat_mex_list_eq_zeroIf a list of naturals does not contain 0, then its mex (minimum excluded value) is 0.
- nat_mex_list_append_commFor any two lists of natural numbers l1 and l2, nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
- spider_mex_list_eq_of_not_mem_and_lt_memIf a natural number m is absent from a list l of naturals and every k < m is present in l, then the mex of l is m.
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.
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.
induction fuel generalizing n with | zero => right exact ⟨rfl, fun k h1 h2 => by omega⟩
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.
| 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 ∈ lIf 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.
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
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.
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)
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.
uses
if_neg· rw [if_neg hn] left exact ⟨hn, fun k hk1 hk2 => by omega⟩
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.
uses
nat_mex_list_not_mem_and_lt_loop_spec,Nat.zero_lechange (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⟩
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`.
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)
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.
uses
List.Nodup.length_le_of_subset,List.nodup_range,List.length_rangehave 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.
- The function `nat_mex_list` is defined using a fuel-bounded helper `loop` to satisfy Lean's termination checker; setting fuel to `l.length + 1` ensures that the loop cannot exhaust its fuel without violating the pigeonhole principle for lists.
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.
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