AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Functions.Disjointness.foolingSet

defimported Lean

The candidate fooling set for disjointness is the collection of all pairs $(X, X^c)$ where $X \subseteq [n]$, i.e.\ $\mathrm{foolingSet}(n) = \{(X, Y) \mid Y = X^c\}$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open scoped symmDiff in
def CommunicationComplexity.Functions.Disjointness.foolingSet (n : ℕ) : Set (Set (Fin n) × Set (Fin n))
Defined in
TCSlib, `CommunicationComplexity.Functions.Disjointness.foolingSet`
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 2

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open scoped symmDiff in
/-- The fooling set for disjointness: the set of all pairs `(X, Xᶜ)` of a subset of `[n]` and its complement [RY20, Ch. 1, §Using Fooling Sets]. -/
def CommunicationComplexity.Functions.Disjointness.foolingSet (n : ℕ) : Set (Set (Fin n) × Set (Fin n)) :=
  {p | p.2 = p.1ᶜ}
See it in the graphDiscuss this resultChallenge it