AFTD Auto-Formalizing Theoretical Domains

cover_number

def

The $b$-monochromatic cover number $\mathrm{cover\_number}(f, b)$ of a curried Boolean function $f : X \to Y \to \mathrm{Bool}$ is the extended natural number in $\mathrm{ENat}$ defined as the infimum of $C.\mathrm{encard}$ over all collections $C : \mathrm{Set}\;(\mathrm{Set}\;(X \times Y))$ satisfying $\mathrm{is\_monochromatic\_cover}\;C\;f\;b$.

Statement

noncomputable def cover_number {X Y : Type*} (f : X → Y → Bool) (b : Bool) : ENat
Defined in
arXiv:2611.11488, Section 1.1
Verified
10 Nov 2026
Axioms
none listed
Built on 1
  • is_monochromatic_coverGiven types $X$ and $Y$, a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, and a Boolean value $b : \mathrm{Bool}$, a collection…

Read back from the Lean

For types X and Y, a function f : X → Y → Bool, and a Boolean b : Bool, cover_number f b is defined as the infimum in ENat of C.encard (the extended cardinality of C) over all sets of sets C : Set (Set (X × Y)) satisfying is_monochromatic_cover C f b (evaluating to ⊤ if no such cover exists).

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 number of b-monochromatic rectangles needed to cover f⁻¹(b). -/
noncomputable def cover_number {X Y : Type*} (f : X → Y → Bool) (b : Bool) : ENat := ⨅ (C : Set (Set (X × Y))) (_ : is_monochromatic_cover C f b), C.encard
See it in the graphDiscuss this resultChallenge it