AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Rectangle.monoPartition_values_eq

theoremverifiedimported Lean

Constant values within a part. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function $g : X \to Y \to \alpha$, and let $R \in \mathcal{P}$. Then $g$ is constant on $R$: for any $(x,y), (x',y') \in R$ we have $g\,x\,y = g\,x'\,y'$.

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_values_eq (h : IsMonoPartition Part g)
    {R : Set (X × Y)} (hR : R ∈ Part)
    {x x' : X} {y y' : Y}
    (hxy : (x, y) ∈ R) (hx'y' : (x', y') ∈ R) :
    g x y = g x' y'
Source
TCSlib, `CommunicationComplexity.Rectangle.monoPartition_values_eq`
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 3

Lean source view module on GitHub

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
/-- In a monochromatic rectangle partition, any two points in the same part have equal function values. -/
theorem CommunicationComplexity.Rectangle.monoPartition_values_eq (h : IsMonoPartition Part g)
    {R : Set (X × Y)} (hR : R ∈ Part)
    {x x' : X} {y y' : Y}
    (hxy : (x, y) ∈ R) (hx'y' : (x', y') ∈ R) :
    g x y = g x' y' :=
  h.2.1 R hR x x' y y' hxy hx'y'
See it in the graphDiscuss this resultChallenge it