AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Rectangle.IsFoolingSet

defimported Lean

A 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$ contains at most one point of $S$, i.e., $S \cap R$ is a subsingleton for every rectangle $R$ that is monochromatic for $g$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
def CommunicationComplexity.Rectangle.IsFoolingSet (S : Set (X × Y)) (g : X → Y → α) : Prop
Defined in
TCSlib, `CommunicationComplexity.Rectangle.IsFoolingSet`
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
Built on 2
Used by 5

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- A set `S ⊆ X × Y` is a fooling set for `g` if every monochromatic rectangle with respect to `g` contains at most one point of `S`. [Rou16, §4.2.5 Definition (fooling set)]. Deviation: Rou16 define a fooling set by the two conditions "`g` is constant on `S`" and "for distinct points of `S`, one of the two mixed pairs has a different `g`-value"; the definition here is the consequence those conditions are used for (every monochromatic rectangle meets `S` in at most one point), which is all the counting bound needs. -/
def CommunicationComplexity.Rectangle.IsFoolingSet (S : Set (X × Y)) (g : X → Y → α) : Prop :=
  ∀ R : Set (X × Y), IsRectangle R → IsMonochromatic R g →
    (S ∩ R).Subsingleton
See it in the graphDiscuss this resultChallenge it