AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Rectangle.IsRectangle

defimported Lean

A subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and $B \subseteq Y$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
def CommunicationComplexity.Rectangle.IsRectangle (S : Set (X × Y)) : Prop
Defined in
TCSlib, `CommunicationComplexity.Rectangle.IsRectangle`
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
none listed
Used by 13

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- A subset of `X × Y` is a (combinatorial) rectangle if it is a product `A ×ˢ B` of a set of `X`-inputs and a set of `Y`-inputs. [RY20, Ch. 1, 'Rectangles'] / [Rou16, §4.2.4 Definition (rectangle)]. -/
def CommunicationComplexity.Rectangle.IsRectangle (S : Set (X × Y)) : Prop :=
  ∃ A : Set X, ∃ B : Set Y, S = A ×ˢ B
See it in the graphDiscuss this resultChallenge it