AFTD Auto-Formalizing Theoretical Domains

nat_mex_set_eq_one_of_mem

theoremverified

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

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.

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

    lines 2–5

    uses Nat.sInf_mem, Nat.sInf_le

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

    lines 6–8

    uses Nat.le_one_iff_eq_zero_or_eq_one.mp

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

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