AFTD Auto-Formalizing Theoretical Domains

nat_mex_set_ne_of_mem

theoremverified

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

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.

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

    lines 2–3

      unfold nat_mex_set
      intro h
  2. 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.

    line 4

      have hne : ({n : ℕ | n ∉ s} : Set ℕ).Nonempty := hs.infinite_compl.nonempty
  3. A 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.

    lines 5–7

    uses Nat.sInf_mem

      have 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

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