AFTD Auto-Formalizing Theoretical Domains

is_monochromatic_cover

def

Given types $X$ and $Y$, a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, and a Boolean value $b : \mathrm{Bool}$, a collection $C : \mathrm{Set}\;(\mathrm{Set}\;(X \times Y))$ is a $b$-monochromatic rectangle cover of $f^{-1}(b)$ if every $R \in C$ satisfies $\mathrm{CommunicationComplexity.Rectangle.IsRectangle}\;R$, for every $R \in C$ and $(x,y) \in R$ we have $f\;x\;y = b$, and $\{p : X \times Y \mid f\;p.1\;p.2 = b\} \subseteq \bigcup C$.

Statement

def is_monochromatic_cover {X Y : Type*} (C : Set (Set (X × Y))) (f : X → Y → Bool) (b : Bool) : Prop
Defined in
arXiv:2611.11488, Section 1.1
Verified
10 Nov 2026
Axioms
none listed
Built on 1
Used by 1
  • cover_numberThe $b$-monochromatic cover number $\mathrm{cover\_number}(f, b)$ of a curried Boolean function $f : X \to Y \to \mathrm{Bool}$ is the…

Read back from the Lean

Given types X and Y, a family of subsets C : Set (Set (X × Y)), a function f : X → Y → Bool, and a boolean b : Bool, is_monochromatic_cover C f b is defined as the conjunction of three conditions: 1. Every element R ∈ C satisfies CommunicationComplexity.Rectangle.IsRectangle R. 2. Every element R ∈ C is monochromatic with value b: for all R ∈ C and all x : X and y : Y, if (x, y) ∈ R, then f x y = b. 3. The sets in C cover all inputs where f evaluates to b: the set {p : X × Y | f p.1 p.2 = b} is a subset of the union ⋃₀ C (that is, every (x, y) with f x y = b belongs to at least one R ∈ C).

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

/-- Predicate stating that C is a collection of b-monochromatic rectangles covering f⁻¹(b). -/
def is_monochromatic_cover {X Y : Type*} (C : Set (Set (X × Y))) (f : X → Y → Bool) (b : Bool) : Prop :=
  (∀ R ∈ C, CommunicationComplexity.Rectangle.IsRectangle R) ∧
  (∀ R ∈ C, ∀ x y, (x, y) ∈ R → f x y = b) ∧
  {p : X × Y | f p.1 p.2 = b} ⊆ ⋃₀ C
See it in the graphDiscuss this resultChallenge it