nat_mex_set_eq_one_of_mem
If 0 is in a set s of natural numbers and 1 is not, the mex of s is 1.
Statement
theorem nat_mex_set_eq_one_of_mem {s : Set ℕ} (h0 : 0 ∈ s) (h1 : 1 ∉ s) : nat_mex_set s = 1- Source
- Helper for arrows_parity_of_threads_le_two, arXiv:2610.15145 Theorem 10.3 / Corollary 10.4 (the induction in the proof of Theorem 10.3: every option has value (e-1) mod 2 or an option of value e mod 2), done directly on positions of T without the sum decomposition
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- nat_mex_setThe minimum excluded natural number of a set s of natural numbers is the infimum of the set of natural numbers not in s.
- Used by 1
- arrows_pos_grundy_eq_mod_two_of_classStrategy lemma for parity in the Game of Arrows: let e be a function on positions that drops by exactly one along every legal move, and S…
The proof, explained
By definition, the minimum excluded value (mex) of a set of natural numbers s is the least natural number not in s. Because 1 ∉ s, the set of omitted numbers contains 1, which bounds its infimum above by 1. That leaves only 0 and 1 as possible values; the hypothesis 0 ∈ s rules out 0 by contradiction, leaving 1.
The infimum of the complement {n ∈ ℕ | n ∉ s} belongs to the complement and is at most 1.
Unfolding the definition of nat_mex_set, the mex is the infimum of {n ∈ ℕ | n ∉ s}. Since 1 ∉ s (h1), this set of omitted natural numbers is nonempty, witnessed by 1 (hne). By Nat.sInf_mem, the infimum of any nonempty set of natural numbers belongs to the set, so the infimum is not in s (hmem). Furthermore, by Nat.sInf_le, the infimum is bounded above by any element of the set, so it is at most 1 (hle).
uses
Nat.sInf_mem,Nat.sInf_leunfold nat_mex_set have hne : ({n : ℕ | n ∉ s} : Set ℕ).Nonempty := ⟨1, h1⟩ have hmem := Nat.sInf_mem hne have hle : sInf {n : ℕ | n ∉ s} ≤ 1 := Nat.sInf_le h1
The infimum equals 1, completing the proof.
Since the infimum is at most 1, it must be either 0 or 1 by Nat.le_one_iff_eq_zero_or_eq_one.mp. In the case where the infimum is 0, substituting 0 into the membership fact hmem gives 0 ∉ s, which directly contradicts the hypothesis 0 ∈ s (h0). This eliminates 0, so the remaining case yields that the infimum is 1, which matches the goal.
uses
Nat.le_one_iff_eq_zero_or_eq_one.mprcases Nat.le_one_iff_eq_zero_or_eq_one.mp hle with h | h · rw [h] at hmem; exact absurd h0 hmem · exact h
Nat.sInf_mem- The infimum of a nonempty set of natural numbers belongs to the set.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in the set.
Nat.le_one_iff_eq_zero_or_eq_one.mp- If a natural number is less than or equal to 1, then it equals 0 or it equals 1.
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.
theorem nat_mex_set_eq_one_of_mem {s : Set ℕ} (h0 : 0 ∈ s) (h1 : 1 ∉ s) : nat_mex_set s = 1 := by unfold nat_mex_set have hne : ({n : ℕ | n ∉ s} : Set ℕ).Nonempty := ⟨1, h1⟩ have hmem := Nat.sInf_mem hne have hle : sInf {n : ℕ | n ∉ s} ≤ 1 := Nat.sInf_le h1 rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hle with h | h · rw [h] at hmem; exact absurd h0 hmem · exact h