CommunicationComplexity.Rectangle.foolingSet_ncard_le_of_monoPartition
theoremverifiedimported Lean
Fooling set bound via monochromatic partition. Let $g : X \times Y \to \alpha$, let $S \subseteq X \times Y$ be a fooling set for $g$, and let $\mathcal{P}$ be a monochromatic rectangle partition for $g$. If $\mathcal{P}$ is finite, then the number of points of $S$ is at most the number of members of $\mathcal{P}$; that is, $\abs{S} \le \abs{\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.foolingSet_ncard_le_of_monoPartition {S : Set (X × Y)} (hS : IsFoolingSet S g) (hPart : IsMonoPartition Part g) (hfin : Part.Finite) : Set.ncard S ≤ Set.ncard Part
- Source
- TCSlib, `CommunicationComplexity.Rectangle.foolingSet_ncard_le_of_monoPartition`
- 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.foolingSet_ncard_le_of_monoPartition← CommunicationComplexity.Rectangle.foolingSet_ncard_le_of_monoPartition (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:171): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.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…
- CommunicationComplexity.Rectangle.IsFoolingSetA set $S \subseteq X \times Y$ is a fooling set for $g : X \to Y \to \alpha$ if every monochromatic rectangle with respect to $g$…
- Used by 1
- CommunicationComplexity.Deterministic.foolingSet_ncard_le_pow_of_communicationComplexity_leFooling set bound from communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
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/-- Any finite monochromatic rectangle partition has at least as many parts as any fooling set for the same function (as natural-number cardinalities; the fooling set is then finite too). [Rou16, Cor 4.7] (its proof: each fooling-set element needs its own monochromatic rectangle); see `foolingSet_encard_le_of_monoPartition` for the deviation. -/theorem CommunicationComplexity.Rectangle.foolingSet_ncard_le_of_monoPartition {S : Set (X × Y)} (hS : IsFoolingSet S g) (hPart : IsMonoPartition Part g) (hfin : Part.Finite) : Set.ncard S ≤ Set.ncard Part := by have henc := foolingSet_encard_le_of_monoPartition hS hPart have hSfin : S.Finite := hfin.finite_of_encard_le henc simpa [Set.ncard] using ENat.toNat_le_toNat henc hfin.encard_lt_top.ne