CommunicationComplexity.Rectangle.monoPartition_point_mem
theoremverifiedimported Lean
Every point lies in some part of a partition. Let $g : X \times Y \to \alpha$ and let $\mathcal{P}$ be a monochromatic rectangle partition for $g$. Then every point $p \in X \times Y$ belongs to at least one member $R \in \mathcal{P}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in variable {Part : Set (Set (X × Y))} {g : X → Y → α} in theorem CommunicationComplexity.Rectangle.monoPartition_point_mem (h : IsMonoPartition Part g) (p : X × Y) : ∃ R ∈ Part, p ∈ R
- Source
- TCSlib, `CommunicationComplexity.Rectangle.monoPartition_point_mem`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Rectangle.monoPartition_point_mem← CommunicationComplexity.Rectangle.monoPartition_point_mem (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:114): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- CommunicationComplexity.Rectangle.IsMonoPartitionA collection $\mathcal{P}$ of subsets of $X \times Y$ is a monochromatic rectangle partition for $g : X \to Y \to \alpha$ if every…
- Used by 5
- CommunicationComplexity.Rectangle.foolingSet_encard_le_of_monoPartitionFooling set bound from a monochromatic rectangle partition. Let $X$, $Y$, and $\alpha$ be sets and let $g : X \times Y \to \alpha$. If…
- CommunicationComplexity.Functions.Equality.le_communicationComplexityDeterministic complexity lower bound for equality. For every natural number $n \ge 1$, the deterministic communication complexity of the…
- CommunicationComplexity.Deterministic.Protocol.sum_indicator_leafRectangles_eqIndicator sum over leaf rectangles recovers the protocol output. Let $X$ and $Y$ be input types whose product $X \times Y$ carries a…
- CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncardRank bounded by monochromatic partition size. Let $X$ be a finite set, $Y$ a finite set, and $f : X \to Y \to \mathrm{Bool}$ a Boolean…
- CommunicationComplexity.Functions.Disjointness.le_communicationComplexityLower bound on the communication complexity of disjointness. Fix an integer $n \ge 1$, and consider the set-disjointness function on…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} invariable {Part : Set (Set (X × Y))} {g : X → Y → α} in/-- Every point of `X × Y` lies in some member of a monochromatic rectangle partition. -/theorem CommunicationComplexity.Rectangle.monoPartition_point_mem (h : IsMonoPartition Part g) (p : X × Y) : ∃ R ∈ Part, p ∈ R := by have := h.2.2.1 ▸ Set.mem_univ p exact Set.mem_sUnion.mp this