TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-13

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 $A_{0}, \dots, A_{n - 1}$ , $P ⁣ (⋃_{i < n} A_{i}) \leq \sum_{i < n} P (A_{i}) .$ For $n = 0$ both sides are $0$ .

Facts & Assumptions

Given: A finite probability space and events $A_{0}, \dots, A_{n - 1}$ .

[L1]

Probability is monotone under inclusion (Normalization, nonnegativity, monotonicity, complements, and differences in a finite probability space).

[L2]

Probability is additive on finite pairwise-disjoint families (Probability is additive on every finite pairwise-disjoint family of events).

Proof

technique · direct

1.1

For $i < n$ , put $B_{i} = A_{i} ∖ ⋃_{j < i} A_{j}$ . Then the $B_{i}$ are pairwise disjoint, $B_{i} \subseteq A_{i}$ , and $⋃_{i < n} B_{i} = ⋃_{i < n} A_{i}$ .

construct

2.1

Hence $P (⋃_{i < n} A_{i}) = \sum_{i < n} P (B_{i}) \leq \sum_{i < n} P (A_{i})$ .

step 1.1L1L2algebra

3.1

For $n = 0$ step 2.1 reads $0 \leq 0$ , and for $n = 1$ it is equality.

step 2.1∎

Depends on

Used by

Dependency tree · two levels

6 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

J. Matousek and J. Vondrak, The Probabilistic Method, Lemma 1.1.3 (standard reference, not scraped)
H. Pishro-Nik, Introduction to Probability, Statistics, and Random Processes, Section 6.2.1 (standard reference, not scraped)