Proof of Bonferroni Inequalities
Definitions and Notation.
A measure space is a triple , where is a set, is a -algebra over , and is a measure, that is, a non-negative function that is countably additive. If , the characteristic function of is the function defined by if , if . A unimodal sequence is a sequence of real numbers for which there is an index such that for and for .
The proof of the following easy lemma is left to the reader:
If is a unimodal sequence of non-negative real numbers with , then for even and for odd .
If is a positive integer, for even and for odd .
Let be a sequence of sets and let . For , let be the set of indices such that . If ,
for all .
if , and otherwise. Therefore the sum equals the number of -subsets of , which is . ∎