is_monochromatic_cover_all
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
- CommunicationComplexity.Rectangle.IsRectangleA subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and…
- CommunicationComplexity.Rectangle.IsMonochromaticA set $S \subseteq X \times Y$ is monochromatic for a function $g : X \to Y \to \alpha$ if $g$ is constant on $S$, i.e.,…
- 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