nat_mex_set_ne_of_mem
The mex of a finite set s of natural numbers is not an element of s.
Statement
theorem nat_mex_set_ne_of_mem {s : Set ℕ} (hs : s.Finite) {k : ℕ} (hk : k ∈ s) : nat_mex_set s ≠ k- 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
The theorem is proved by contradiction: suppose the mex of a finite set s ⊆ ℕ equals an element k ∈ s. By definition, nat_mex_set s is the infimum of the complement {n : ℕ | n ∉ s}, which is infinite (and thus nonempty) because s is finite. Applying Nat.sInf_mem shows that this infimum belongs to the complement, which implies k ∉ s, directly contradicting k ∈ s.
Assume for contradiction that nat_mex_set s = k.
Unfolding the definition of nat_mex_set, the goal becomes sInf {n : ℕ | n ∉ s} ≠ k. We assume for contradiction that this infimum is equal to k.
unfold nat_mex_set intro h
The complement {n : ℕ | n ∉ s} is nonempty.
Because s is a finite subset of the infinite set ℕ, its complement is infinite, and every infinite set is nonempty.
have hne : ({n : ℕ | n ∉ s} : Set ℕ).Nonempty := hs.infinite_compl.nonemptyA contradiction is reached: k ∉ s and k ∈ s.
By Nat.sInf_mem, the nonempty set {n : ℕ | n ∉ s} contains its infimum, so sInf {n : ℕ | n ∉ s} ∉ s. Substituting the assumed equality sInf {n : ℕ | n ∉ s} = k into this membership statement yields k ∈ {n : ℕ | n ∉ s}, which means k ∉ s. This contradicts the given hypothesis that k ∈ s.
uses
Nat.sInf_memhave hmem := Nat.sInf_mem hne rw [h] at hmem exact hmem hk
Nat.sInf_mem- Every nonempty set of natural numbers contains its infimum (its minimum element).
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_ne_of_mem {s : Set ℕ} (hs : s.Finite) {k : ℕ} (hk : k ∈ s) : nat_mex_set s ≠ k := by unfold nat_mex_set intro h have hne : ({n : ℕ | n ∉ s} : Set ℕ).Nonempty := hs.infinite_compl.nonempty have hmem := Nat.sInf_mem hne rw [h] at hmem exact hmem hk