# 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)$$

-

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.

-