Proof using induction

Boole's inequality may be proved for finite collections of ${\displaystyle n}$ events using the method of induction.

For the ${\displaystyle n=1}$ case, it follows that

${\displaystyle \mathbb {P} (A_{1})\leq \mathbb {P} (A_{1}).}$

For the case ${\displaystyle n}$, we have

${\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{i=1}^{n}{\mathbb {P} }(A_{i}).}$

Since ${\displaystyle \mathbb {P} (A\cup B)=\mathbb {P} (A)+\mathbb {P} (B)-\mathbb {P} (A\cap B),}$ and because the union operation is associative, we have

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)+\mathbb {P} (A_{n+1})-\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\cap A_{n+1}\right).}$

Since

${\displaystyle {\mathbb {P} }\left(\bigcup _{i=1}^{n}A_{i}\cap A_{n+1}\right)\geq 0,}$

by the first axiom of probability, we have

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)\leq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)+\mathbb {P} (A_{n+1}),}$

and therefore

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n+1}A_{i}\right)\leq \sum _{i=1}^{n}\mathbb {P} (A_{i})+\mathbb {P} (A_{n+1})=\sum _{i=1}^{n+1}\mathbb {P} (A_{i}).}$

Proof without using induction

For any events in ${\displaystyle A_{1},A_{2},A_{3},\dots }$in our probability space we have

${\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)\leq \sum _{i}\mathbb {P} (A_{i}).}$

One of the axioms of a probability space is that if ${\displaystyle B_{1},B_{2},B_{3},\dots }$ are disjoint subsets of the probability space then

${\displaystyle \mathbb {P} \left(\bigcup _{i}B_{i}\right)=\sum _{i}\mathbb {P} (B_{i});}$

this is called countable additivity.

If we modify the sets ${\displaystyle A_{i}}$, so they become disjoint,

${\displaystyle B_{i}=A_{i}-\bigcup _{j=1}^{i-1}A_{j}}$

we can show that

${\displaystyle \bigcup _{i=1}^{\infty }B_{i}=\bigcup _{i=1}^{\infty }A_{i}.}$

by proving both directions of inclusion.

Suppose ${\displaystyle x\in \bigcup _{i=1}^{\infty }A_{i}}$. Then ${\displaystyle x\in A_{k}}$ for some minimum ${\displaystyle k}$ such that ${\displaystyle i<k\implies x\notin A_{i}}$. Therefore ${\displaystyle x\in B_{k}=A_{k}-\bigcup _{j=1}^{k-1}A_{j}}$. So the first inclusion is true: ${\displaystyle \bigcup _{i=1}^{\infty }A_{i}\subset \bigcup _{i=1}^{\infty }B_{i}}$.

Next suppose that ${\displaystyle x\in \bigcup _{i=1}^{\infty }B_{i}}$. It follows that ${\displaystyle x\in B_{k}}$ for some ${\displaystyle k}$. And ${\displaystyle B_{k}=A_{k}-\bigcup _{j=1}^{k-1}A_{j}}$ so ${\displaystyle x\in A_{k}}$, and we have the other inclusion: ${\displaystyle \bigcup _{i=1}^{\infty }B_{i}\subset \bigcup _{i=1}^{\infty }A_{i}}$.

By construction of each ${\displaystyle B_{i}}$, ${\displaystyle B_{i}\subset A_{i}}$. For ${\displaystyle B\subset A,}$ it is the case that ${\displaystyle \mathbb {P} (B)\leq \mathbb {P} (A).}$

So, we can conclude that the desired inequality is true:

${\displaystyle \mathbb {P} \left(\bigcup _{i}A_{i}\right)=\mathbb {P} \left(\bigcup _{i}B_{i}\right)=\sum _{i}\mathbb {P} (B_{i})\leq \sum _{i}\mathbb {P} (A_{i}).}$

Proof for odd K

Let ${\displaystyle E=\bigcap _{i=1}^{n}B_{i}}$, where ${\displaystyle B_{i}\in \{A_{i},A_{i}^{c}\}}$ for each ${\displaystyle i=1,\dots ,n}$. These such ${\displaystyle E}$ partition the sample space, and for each ${\displaystyle E}$ and every ${\displaystyle i}$, ${\displaystyle E}$ is either contained in ${\displaystyle A_{i}}$ or disjoint from it.

If ${\displaystyle E=\bigcap _{i=1}^{n}A_{i}^{c}}$, then ${\displaystyle E}$ contributes 0 to both sides of the inequality.

Otherwise, assume ${\displaystyle E}$ is contained in exactly ${\displaystyle L}$ of the ${\displaystyle A_{i}}$. Then ${\displaystyle E}$ contributes exactly ${\displaystyle \mathbb {P} (E)}$ to the right side of the inequality, while it contributes

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}{L \choose j}\mathbb {P} (E)}$

to the left side of the inequality. However, by Pascal's rule, this is equal to

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}\left({L-1 \choose j-1}+{L-1 \choose j}\right)\mathbb {P} (E)}$

which telescopes to

${\displaystyle \left(1+{L-1 \choose K}\right)\mathbb {P} (E)\geq \mathbb {P} (E)}$

Thus, the inequality holds for all events ${\displaystyle E}$, and so by summing over ${\displaystyle E}$, we obtain the desired inequality:

${\displaystyle \sum _{j=1}^{K}(-1)^{j-1}S_{j}\geq \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)}$

The proof for even ${\displaystyle K}$ is nearly identical.^[3]

Example

Suppose that you are estimating 5 parameters based on a random sample, and you can control each parameter separately. If you want your estimations of all five parameters to be good with a chance 95%, what should you do to each parameter?

Tuning each parameter's chance to be good to within 95% is not enough because "all are good" is a subset of each event "Estimate i is good". We can use Boole's Inequality to solve this problem. By finding the complement of event "all five are good", we can change this question into another condition:

P( at least one estimation is bad) = 0.05 ≤ P( A₁ is bad) + P( A₂ is bad) + P( A₃ is bad) + P( A₄ is bad) + P( A₅ is bad)

One way is to make each of them equal to 0.05/5 = 0.01, that is 1%. In another word, you have to guarantee each estimate good to 99%( for example, by constructing a 99% confidence interval) to make sure the total estimation to be good with a chance 95%. This is called the Bonferroni Method of simultaneous inference.