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.CommunicationComplexity.Functions.Disjointness.foolingSet← CommunicationComplexity.Functions.Disjointness.foolingSet (TCSlib/CommunicationComplexity/DeterministicCC/FuncDisjointness.lean:71): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 2
- CommunicationComplexity.Functions.Disjointness.foolingSet_isFoolingSetThe disjointness fooling set. Fix $n \in \bbn$, and consider the set-disjointness function on subsets of $[n]$, namely the Boolean…
- CommunicationComplexity.Functions.Disjointness.le_communicationComplexityLower bound on the communication complexity of disjointness. Fix an integer $n \ge 1$, and consider the set-disjointness function on…
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ᶜ}