Metamath Proof Explorer

Theorem boolesineq

Description: Boole's inequality (union bound). For any finite or countable collection of events, the probability of their union is at most the sum of their probabilities. (Suggested by DeepSeek R1.) (Contributed by Ender Ting, 30-Apr-2025)

		Ref	Expression
	Assertion	boolesineq	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to P (⋃_{n \in ℕ} A (n)) \leq \underset{n \in ℕ}{\sum^{*}} P (A (n))$

Proof

Step	Hyp	Ref	Expression
1		domprobmeas	$⊢ P \in Prob \to P \in measures (dom P)$
2	1	adantr	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to P \in measures (dom P)$
3		domprobsiga	$⊢ P \in Prob \to dom P \in ⋃ ran sigAlgebra$
4		simpr	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to A : ℕ ⟶ dom P$
5	4	ffvelcdmda	$⊢ ((P \in Prob \land A : ℕ ⟶ dom P) \land n \in ℕ) \to A (n) \in dom P$
6	5	ralrimiva	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to \forall n \in ℕ A (n) \in dom P$
7		sigaclcu2	$⊢ (dom P \in ⋃ ran sigAlgebra \land \forall n \in ℕ A (n) \in dom P) \to ⋃_{n \in ℕ} A (n) \in dom P$
8	3 6 7	syl2an2r	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to ⋃_{n \in ℕ} A (n) \in dom P$
9		ssidd	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to ⋃_{n \in ℕ} A (n) \subseteq ⋃_{n \in ℕ} A (n)$
10	2 8 5 9	measiun	$⊢ (P \in Prob \land A : ℕ ⟶ dom P) \to P (⋃_{n \in ℕ} A (n)) \leq \underset{n \in ℕ}{\sum^{*}} P (A (n))$