Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adapted
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The finite union bound

Statement

For every finite family of events A0,…,An−1, P ⁣(⋃i<nAi)≤∑i<nP(Ai). For n=0 both sides are 0.

Facts & Assumptions

Given: A probability space (Ω,F,P) and events A0,…,An−1∈F, where n≥0 is an integer.

[L1]

A probability measure is a measure on its event sigma-algebra, with total mass one (Probability measures and probability spaces).

[L2]

If μ is a measure and B⊆A are measurable, then μ(B)≤μ(A) (Measures are monotone).

[L3]

A measure assigns zero to the empty set and is countably additive on pairwise-disjoint measurable sequences (Measures on sigma-algebras).

[L4]

A sigma-algebra is an algebra of subsets, so it contains the empty set and is closed under finite unions and differences (Sigma-algebras).

Proof

technique · disjointify the finite family and apply general measure additivity and monotonicity
1.1givenL4construct

For i<n, put Bi=Ai∖⋃j<iAj. By [L4], every Bi is measurable. They are pairwise disjoint and satisfy Bi⊆Ai. Their union equals ⋃i<nAi: a point in the latter has a least index i<n at which it belongs to Ai, and then belongs to Bi; the reverse inclusion follows from Bi⊆Ai.

2.1step 1.1L1L2L3algebra

By [L1], P is a measure. Extend the disjoint family by Bi=∅ for i≥n. Countable additivity and P(∅)=0 from [L3] give P(⋃i<nAi)=∑i<nP(Bi). By [L2], each P(Bi)≤P(Ai), so summing these finitely many inequalities proves P(⋃i<nAi)≤∑i<nP(Ai).

3.1step 2.1L3∎

If n=0, the union is empty and the sum is the empty sum, so both sides are 0 by [L3]. If n=1, the bound is the equality P(A0)=P(A0). These arguments impose no finiteness assumption on Ω.

Depends on

Used by

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources