nat_mex_set_eq_zero_of_not_mem
If 0 is not in a set s of natural numbers, the mex of s is 0.
Statement
theorem nat_mex_set_eq_zero_of_not_mem {s : Set ℕ} (h : 0 ∉ s) : nat_mex_set s = 0- 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 mex of a set $s \subseteq \mathbb{N}$ is the infimum of the natural numbers not in $s$. Since $0 \notin s$, $0$ belongs to this complement, which bounds the infimum from above by $0$. Because any natural number at most $0$ must be $0$, the mex equals $0$.
It suffices to show that $\inf \{n \in \mathbb{N} \mid n \notin s\} = 0$.
Unfold the definition of `nat_mex_set s`, which is defined as the infimum (the least element) of the set of natural numbers not belonging to $s$.
unfold nat_mex_set$\inf \{n \in \mathbb{N} \mid n \notin s\} = 0$
By the hypothesis $h$ ($0 \notin s$), $0$ belongs to the set $\{n \in \mathbb{N} \mid n \notin s\}$. Therefore, by `Nat.sInf_le`, the infimum of this set is at most $0$. Since any natural number bounded above by $0$ is $0$ by `Nat.eq_zero_of_le_zero`, the infimum equals $0$.
uses
Nat.eq_zero_of_le_zero,Nat.sInf_leexact Nat.eq_zero_of_le_zero (Nat.sInf_le (by simpa using h))
Nat.eq_zero_of_le_zero- A natural number less than or equal to 0 is equal to 0.
Nat.sInf_le- If a natural number belongs to a set, the infimum of that set is less than or equal to that number.
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_zero_of_not_mem {s : Set ℕ} (h : 0 ∉ s) : nat_mex_set s = 0 := by unfold nat_mex_set exact Nat.eq_zero_of_le_zero (Nat.sInf_le (by simpa using h))