AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Rectangle.monoPartition_part_unique

theoremverifiedimported Lean

Uniqueness of the part containing a point. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function $g : X \to Y \to \alpha$, and let $R, S \in \mathcal{P}$. If some point $p \in X \times Y$ lies in both $R$ and $S$, then $R = S$.

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_part_unique (h : IsMonoPartition Part g)
    {R S : Set (X × Y)} (hR : R ∈ Part) (hS : S ∈ Part)
    {p : X × Y} (hp1 : p ∈ R) (hp2 : p ∈ S) : R = S
Source
TCSlib, `CommunicationComplexity.Rectangle.monoPartition_part_unique`
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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {X Y α : Type*} invariable {Part : Set (Set (X × Y))} {g : X → Y → α} in/-- If a point lies in two members of a monochromatic rectangle partition, the two members are equal. -/theorem CommunicationComplexity.Rectangle.monoPartition_part_unique (h : IsMonoPartition Part g)    {R S : Set (X × Y)} (hR : R ∈ Part) (hS : S ∈ Part)    {p : X × Y} (hp1 : p ∈ R) (hp2 : p ∈ S) : R = S := by  by_contra hne  exact Set.disjoint_left.mp (h.2.2.2 R S hR hS hne) hp1 hp2
See it in the graphDiscuss this resultChallenge it