AFTD Auto-Formalizing Theoretical Domains

finset_mex

deforiginal

The minimum excluded natural number (mex) of a finite set of natural numbers s, defined as the smallest natural number not belonging to s.

Statement

def finset_mex (s : Finset ℕ) : ℕ
Related work
folklore
Verified
14 Nov 2026
Axioms
none listed
Used by 2
  • op_1600_slow_exact_nim_bounded_grundyIn the normal-play game of slow exact k-Nim on k+2 piles, for every integer k ≥ 3, the range of the Sprague-Grundy function is bounded:…
  • slow_exact_nim_grundy_compFor natural numbers k and n, fuel : ℕ, and position x : Fin n → ℕ, the fuel-bounded Sprague-Grundy value slow_exact_nim_grundy_comp k n…

Read back from the Lean

Definition of finset_mex: given a finite set of natural numbers s, finset_mex s is defined as the first element in the list List.range (s.card + 1) (i.e., the integers 0, 1, ..., s.card in increasing order) that does not belong to s, defaulting to 0 if no such element is found (which cannot happen by the pigeonhole principle). This computes the minimum excluded value (mex) of s.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The minimum excluded natural number (mex) of a finite set of natural numbers. -/
def finset_mex (s : Finset ℕ) : ℕ := ((List.range (s.card + 1)).find? (fun x => ¬(x ∈ s))).getD 0
See it in the graphDiscuss this resultChallenge it