AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
none listed
Used by 4

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)
See it in the graphDiscuss this resultChallenge it