CommunicationComplexity.Rectangle.IsRectangle_iff
theoremverifiedimported Lean
Cross characterization of combinatorial rectangles. A subset $R \subseteq X \times Y$ is a rectangle — that is, $R = A \times B$ for some $A \subseteq X$ and $B \subseteq Y$ — if and only if it is closed under crossing: for all $x, x' \in X$ and $y, y' \in Y$, whenever $(x, y) \in R$ and $(x', y') \in R$, both mixed pairs $(x', y)$ and $(x, y')$ also lie in $R$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in theorem CommunicationComplexity.Rectangle.IsRectangle_iff (R : Set (X × Y)) : IsRectangle R ↔ ∀ x x' y y', (x, y) ∈ R → (x', y') ∈ R → (x', y) ∈ R ∧ (x, y') ∈ R
- Source
- TCSlib, `CommunicationComplexity.Rectangle.IsRectangle_iff`
- 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.IsRectangle_iff← CommunicationComplexity.Rectangle.IsRectangle_iff (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:68): verbatim
- Verified
- 07 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- 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…
- Used by 3
- LinearPMap.closure_smulLinearPMap.closure_smul
- CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSetThe disjointness fooling set. Fix $n \in \bbn$, and consider the set-disjointness function on subsets of $[n]$, namely the Boolean…
- CommunicationComplexity.Rectangle.monoPartition_cross_memCross closure within a part. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function $g : X \to Y \to \alpha$, 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*} in/-- A set `R ⊆ X × Y` is a rectangle if and only if it has the cross property: whenever `(x, y)` and `(x', y')` lie in `R`, so do the mixed pairs `(x', y)` and `(x, y')`. [RY20, Lemma 1.5]. -/theorem CommunicationComplexity.Rectangle.IsRectangle_iff (R : Set (X × Y)) : IsRectangle R ↔ ∀ x x' y y', (x, y) ∈ R → (x', y') ∈ R → (x', y) ∈ R ∧ (x, y') ∈ R := by constructor · rintro ⟨A, B, rfl⟩ x x' y y' ⟨hx, hy⟩ ⟨hx', hy'⟩ exact ⟨⟨hx', hy⟩, ⟨hx, hy'⟩⟩ · intro h refine ⟨Prod.fst '' R, Prod.snd '' R, ?_⟩ ext ⟨x, y⟩ simp only [Set.mem_prod, Set.mem_image, Prod.exists] constructor · intro hxy exact ⟨⟨x, y, hxy, rfl⟩, ⟨x, y, hxy, rfl⟩⟩ · rintro ⟨⟨x', y', hx'y', rfl⟩, ⟨x'', y'', hx''y'', rfl⟩⟩ exact (h _ _ _ _ hx'y' hx''y'').2