CommunicationComplexity.FiniteMeasureSpace
classimported Lean
A typeclass for a measurable space $\Omega$ that is simultaneously finite (carries a
Fintype instance) and discrete (every subset is measurable). It deliberately
does not bundle a measure, so that a single type can be equipped with many different
measures.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ProbabilityTheory in class CommunicationComplexity.FiniteMeasureSpace (Ω : Type*) [MeasurableSpace Ω]
- Defined in
- TCSlib, `CommunicationComplexity.FiniteMeasureSpace`
- 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.FiniteMeasureSpace← CommunicationComplexity.FiniteMeasureSpace (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:64): verbatimattribute [instance] CommunicationComplexity.FiniteMeasureSpace.fintype← attribute [instance] CommunicationComplexity.FiniteMeasureSpace.fintype (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:71): verbatimattribute [instance] CommunicationComplexity.FiniteMeasureSpace.discrete← attribute [instance] CommunicationComplexity.FiniteMeasureSpace.discrete (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:72): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 11
- CommunicationComplexity.FiniteMeasureSpace.ofGiven a type $\Omega$ that already carries
FintypeandDiscreteMeasurableSpaceinstances,… - CommunicationComplexity.Deterministic.Protocol.signedBias_eq_sum_rectanglesSigned bias as a sum over leaf rectangles. Let $\mu$ be a finite probability space on $X \times Y$, let $p$ be a deterministic Boolean…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.exists_good_randomnessExistence of good randomness for derandomization. Let $\Omega$ be a finite probability space and let $X$ and $Y$ be finite input sets. Let…
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalErrorSigned correlation and distributional error. Let $X$ and $Y$ be the input types of Alice and Bob, and let $\mu$ be a finite probability…
- CommunicationComplexity.Internal.product_coin_approxProduct-space coin approximation. Let $\Omega_X$ and $\Omega_Y$ be finite probability spaces, and let $\delta > 0$. Give each coin-tape…
- CommunicationComplexity.finiteMeasureSpaceBoolCommunicationComplexity.finiteMeasureSpaceBool
- CommunicationComplexity.finiteMeasureSpacePiCommunicationComplexity.finiteMeasureSpacePi
- CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mulDiscrepancy lower bound on distributional error. Let $\mu$ be a finite probability measure on $X \times Y$, let…
- CommunicationComplexity.finiteMeasureSpaceProdCommunicationComplexity.finiteMeasureSpaceProd
- CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace… - CommunicationComplexity.Internal.single_coin_approxApproximating a finite probability space by fair coin flips. Let $\Omega$ be a finite probability space, and let $\delta > 0$. Then there…
- CommunicationComplexity.FiniteMeasureSpace.ofGiven a type $\Omega$ that already carries
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ProbabilityTheory in /-- A finite measurable space: the type is finite and the measurable structure is discrete. This deliberately does not include a measure. -/ class CommunicationComplexity.FiniteMeasureSpace (Ω : Type*) [MeasurableSpace Ω] where fintype : Fintype Ω discrete : DiscreteMeasurableSpace Ω attribute [instance] CommunicationComplexity.FiniteMeasureSpace.fintype attribute [instance] CommunicationComplexity.FiniteMeasureSpace.discrete