AFTD Auto-Formalizing Theoretical Domains

is_monochromatic_cover_all

def

Given types $X$ and $Y$ and a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, a collection $C : \mathrm{Set}\;(\mathrm{Set}\;(X \times Y))$ is a monochromatic rectangle cover of all inputs for $f$ if every $R \in C$ satisfies $\mathrm{CommunicationComplexity.Rectangle.IsRectangle}\;R$, every $R \in C$ satisfies $\mathrm{CommunicationComplexity.Rectangle.IsMonochromatic}\;R\;f$, and $\bigcup C = \mathrm{Set.univ}$.

Statement

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

Read back from the Lean

Given types X and Y, a set of sets of pairs C : Set (Set (X × Y)), and a function f : X → Y → Bool, is_monochromatic_cover_all C f asserts that: 1. For every set R ∈ C, CommunicationComplexity.Rectangle.IsRectangle R holds; 2. For every set R ∈ C, CommunicationComplexity.Rectangle.IsMonochromatic R f holds; and 3. The union of all sets in C (⋃₀ C) equals Set.univ (i.e., every pair in X × Y 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 monochromatic rectangle cover of all inputs. -/
def is_monochromatic_cover_all {X Y : Type*} (C : Set (Set (X × Y))) (f : X → Y → Bool) : Prop :=
  (∀ R ∈ C, CommunicationComplexity.Rectangle.IsRectangle R) ∧
  (∀ R ∈ C, CommunicationComplexity.Rectangle.IsMonochromatic R f) ∧
  ⋃₀ C = Set.univ
See it in the graphDiscuss this resultChallenge it