7

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$ ?

Michael Hardy
  • 1
Ashot
  • 4,753
  • 3
  • 34
  • 61

3 Answers3

9

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

Stefan Hansen
  • 25,582
  • 7
  • 59
  • 91
  • 1
    Could you explain, why the last inequality holds? Specifically why it's an inequality and not an equality. – mavavilj Jan 06 '16 at 03:17
  • 1
    @mavavilj: It holds since $B_n\subseteq A_n$ for all $n$. – Stefan Hansen Jan 06 '16 at 06:34
  • Does the strict inequality (or strict subset) hold or just the equality? Why? – mavavilj Jan 06 '16 at 06: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 06 '16 at 06:42
4

You can write out the infinite union as $$ \bigcup_{n=1}^\infty A_n = A_1 \cup (A_2 \cap A_1^c) \cup (A_3 \cap A_1^c \cap 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.

There was a typo. It should be the complement of A_1, not A_2 in the second term.

ArnoF7
  • 3
Cheyne H
  • 931
3

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.$$

By countable additivity we have

$$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.

user15464
  • 11,682