# How to prove Boole’s inequality

I am trying to prove Boole’s inequality

$$P\left(\ \bigcup_{i=1}^\infty A_i\right) \leq \sum_{i=1}^\infty P(A_i).$$

I can show it of any finite $n$ using induction. What to do for $\infty$ ?

-

You can use that $\bigcup_{i=1}^n A_i \uparrow \bigcup_{i=1}^\infty A_i$ for $n\to\infty$ along with the continuity of $P$.

If you want to do it without the use of continuity, then use the construction $$B_1=A_1\quad\text{and}\quad B_n=A_n\setminus \bigcup_{k=1}^{n-1}A_k,\quad n\geq 2$$ to show that $$P \left(\bigcup_{n=1}^\infty A_n\right)=P\left(\bigcup_{n=1}^\infty B_n\right)=\sum_{n=1}^\infty P(B_n)\leq \sum_{n=1}^\infty P(A_n)$$

-
Could you explain, why the last inequality holds? Specifically why it's an inequality and not an equality. – mavavilj Jan 6 at 3:17
@mavavilj: It holds since $B_n\subseteq A_n$ for all $n$. – Stefan Hansen Jan 6 at 6:34
Does the strict inequality (or strict subset) hold or just the equality? Why? – mavavilj Jan 6 at 6:36
@mavavilj: In general, you can only say that $P(B_n)\leq P(A_n)$ when $B_n\subseteq A_n$. Whether it is an equality or strict inequality would depend on the actual $A_n$ and $B_n$. However, we don't really need to this information to conclude the proof. – Stefan Hansen Jan 6 at 6:42

Let $B_1 = A_1$, and inductively define $B_n = A_n \setminus \bigcup_{j=1}^{n-1} B_{n-1}$. Then the $B_n$ are disjoint and

$$\bigcup_{n=1}^\infty B_n = \bigcup_{n=1}^\infty A_n.$$

$$P(\bigcup_{n=1}^\infty B_n) = \sum_{n=1}^\infty P(B_n).$$

By monotonicity $P(B_n) \leq P(A_n)$. Combining these last three relations we get the result.

-

You can write out the infinite union as $$\bigcup_{n=1}^\infty A_n = A_1 \cup (A_1 \cap A_2^c) \cup (A_3 \cap A_1^c A_2^c )\cup \ldots$$

Each of these sets is disjoint, so you can use $\sigma$-additivity. Now just use the fact that the $i$th term is a subset of $A_i$, and so the probability of the $i$th term is less than or equal to the probability of $A_i$.

Disjointness is your best friend in proving this sort of thing.

-