AFTD Auto-Formalizing Theoretical Domains

nat_mex_set_eq_zero_of_not_mem

theoremverified

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

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

  1. 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$.

    line 2

      unfold nat_mex_set
  2. $\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$.

    line 3

    uses Nat.eq_zero_of_le_zero, Nat.sInf_le

      exact 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

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))
See it in the graphDiscuss this resultChallenge it