CommunicationComplexity.Functions.Disjointness.disjointness
defimported Lean
For $n \in \mathbb{N}$ and subsets $X, Y \subseteq [n]$, $\mathrm{disjointness}(n, X, Y)$ is the Boolean function that returns $\mathtt{true}$ if and only if $X$ and $Y$ are disjoint, i.e.\ $X \cap Y = \emptyset$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open scoped symmDiff in noncomputable def CommunicationComplexity.Functions.Disjointness.disjointness (n : ℕ) (X Y : Set (Fin n)) : Bool
- Defined in
- TCSlib, `CommunicationComplexity.Functions.Disjointness.disjointness`
- 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.disjointness← CommunicationComplexity.Functions.Disjointness.disjointness (TCSlib/CommunicationComplexity/DeterministicCC/FuncDisjointness.lean:59): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 4
- 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.communicationComplexity_eqDeterministic complexity of set disjointness. Let $n \geq 1$, and let $\mathrm{disjointness}(n, \cdot, \cdot)$ denote the two-party…
- CommunicationComplexity.Functions.Disjointness.communicationComplexity_leUpper bound on the communication complexity of disjointness. Fix $n \in \bbn$, and let both players' inputs range over subsets of…
- 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 set-disjointness function on subsets of `[n]`: `disjointness n X Y` is `true` if and only if `X ∩ Y = ∅` [RY20, Ch. 1, eq. (1.2)]. -/ noncomputable def CommunicationComplexity.Functions.Disjointness.disjointness (n : ℕ) (X Y : Set (Fin n)) : Bool := by classical exact decide (Disjoint X Y)