CommunicationComplexity.FiniteProbabilitySpace.measureReal_preimage_finset
theoremverifiedimported Lean
Measure of a preimage of a finite set. Let $\Xi$ be a finite probability space and let $\Omega$ be a measurable space in which every subset is measurable. For any map $\varphi \colon \Xi \to \Omega$ and any finite set $T \subseteq \Omega$, the probability that $\varphi$ lands in $T$ decomposes as a sum over the points of $T$: \[ \mathrm{volume}^{\mathbb{R}}\bigl(\varphi^{-1}(T)\bigr) \;=\; \sum_{a \in T} \mathrm{volume}^{\mathbb{R}}\bigl(\varphi^{-1}(\{a\})\bigr), \] where $\mathrm{volume}^{\mathbb{R}}$ denotes the real-valued measure of the underlying probability measure on $\Xi$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open scoped ProbabilityTheory in theorem CommunicationComplexity.FiniteProbabilitySpace.measureReal_preimage_finset {Ξ Ω : Type*} [FiniteProbabilitySpace Ξ] [MeasurableSpace Ω] [DiscreteMeasurableSpace Ω] (φ : Ξ → Ω) (T : Finset Ω) : volume.real (φ ⁻¹' (↑T : Set Ω) : Set Ξ) = ∑ a ∈ T, volume.real (φ ⁻¹' ({a} : Set Ω) : Set Ξ)
- Source
- TCSlib, `CommunicationComplexity.FiniteProbabilitySpace.measureReal_preimage_finset`
- 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.FiniteProbabilitySpace.measureReal_preimage_finset← CommunicationComplexity.FiniteProbabilitySpace.measureReal_preimage_finset (TCSlib/CommunicationComplexity/NewmanTheorem/FiniteProbabilitySpace.lean:414): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
MeasureSpacestructure on $\Omega$ together with aCommunicationComplexity.FiniteMeasureSpace…
- CommunicationComplexity.FiniteProbabilitySpaceA typeclass bundling a
- Used by 3
- 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.FiniteProbabilitySpace.measureReal_finsetAdditivity of the measure over a finite set. Let $\Omega$ be a finite probability space, and let $T$ be a finite subset of $\Omega$.…
- 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…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory inopen scoped ProbabilityTheory in/-- The real-valued measure of the preimage of a finite set splits as a sum over singleton fibers. -/theorem CommunicationComplexity.FiniteProbabilitySpace.measureReal_preimage_finset {Ξ Ω : Type*} [FiniteProbabilitySpace Ξ] [MeasurableSpace Ω] [DiscreteMeasurableSpace Ω] (φ : Ξ → Ω) (T : Finset Ω) : volume.real (φ ⁻¹' (↑T : Set Ω) : Set Ξ) = ∑ a ∈ T, volume.real (φ ⁻¹' ({a} : Set Ω) : Set Ξ) := by rw [Measure.real] rw [show (φ ⁻¹' (↑T : Set Ω) : Set Ξ) = ⋃ a ∈ T, φ ⁻¹' ({a} : Set Ω) from by ext ξ simp] rw [measure_biUnion_finset (fun a _ b _ h => Disjoint.preimage _ (Set.disjoint_singleton.mpr h)) (fun _ _ => MeasurableSet.of_discrete)] rw [ENNReal.toReal_sum (fun _ _ => measure_ne_top _ _)] simp [Measure.real]