Proof of Bonferroni Inequalities

Definitions and Notation.

A measure space is a triple $(X,\\Sigma,\\mu)$ , where $X$ is a set, $\\Sigma$ is a $\\sigma$ -algebra over $X$ , and $\\mu\\colon\\Sigma\\rightarrow[0,\\infty]$ is a measure, that is, a non-negative function that is countably additive. If $A\\in\\Sigma$ , the characteristic function of $A$ is the function $\\chi_{A}\\colon X\\rightarrow\\mathbb{R}$ defined by $\\chi_{A}(x)=1$ if $x\\in A$ , $\\chi_{A}(x)=0$ if $x\otin A$ . A unimodal sequence is a sequence of real numbers $a_{0},a_{1},\\ldots,a_{n}$ for which there is an index $k$ such that $a_{i}\\leq a_{i+1}$ for $i<k$ and $a_{i}\\geq a_{i+1}$ for $i\\geq k$ .

The proof of the following easy lemma is left to the reader:

Lemma 1.

If $a_{0}\\leq a_{1}\\leq\\ldots\\leq a_{k}\\geq a_{k+1}\\geq a_{k+2}\\geq\\ldots\\geq a_{n}$ is a unimodal sequence of non-negative real numbers with $\\sum_{i=0}^{n}(-1)^{i}a_{i}=0$ , then $\\sum_{i=0}^{j}(-1)^{i}a_{i}\\geq 0$ for even $j$ and $\\leq 0$ for odd $j$ .

Since the binomial sequence $(\\binom{a}{i})_{0\\leq i\\leq n}$ with integer $a>0$ and integer $n\\geq a$ satisfies the hypothesis of Lemma 1, we have:

Corollary 1.

If $a$ is a positive integer, $\\sum_{i=0}^{j}(-1)^{i}\\binom{a}{i}\\geq 0$ for even $j$ and $\\leq 0$ for odd $j$ .

Lemma 2.

Let $(A_{i})_{1\\leq i\\leq n}$ be a sequence of sets and let $X=\\bigcup_{1\\leq i\\leq n}A_{i}$ . For $x\\in X$ , let $I(x)$ be the set of indices $j$ such that $x\\in A_{j}$ . If $1\\leq k\\leq n$ ,

\\sum_{1\\leq i_{1}<i_{2}<\\ldots<i_{k}\\leq n}\\chi_{A_{i_{1}}\\cap A_{i_{2}}\\cap%\\ldots\\cap A_{i_{k}}}(x)=\\binom{|I(x)|}{k}

for all $x\\in X$ .

Proof.

$\\chi_{A_{i_{1}}\\cap A_{i_{2}}\\cap\\ldots\\cap A_{i_{k}}}(x)=1$ if $\\{i_{1},i_{2},\\ldots,i_{k}\\}\\subseteq I(x)$ , and $=0$ otherwise. Therefore the sum equals the number of $k$ -subsets of $I(x)$ , which is $\\binom{|I(x)|}{k}$ .∎

Theorem 1.

Let $(X,\\Sigma,\\mu)$ be a measure space. If $(A_{i})_{1\\leq i\\leq n}$ is a finite sequence of measurable sets all having finite measure, and

S_{j}=\\mu(A_{1}\\cup A_{2}\\cup\\ldots\\cup A_{n})+\\sum_{k=1}^{j}(-1)^{k}\\sum_{1%\\leq i_{1}<i_{2}<\\ldots<i_{k}\\leq n}\\mu(A_{i_{1}}\\cap A_{i_{2}}\\cap\\ldots\\cap A%_{i_{k}})

then $S_{j}\\geq 0$ for even $j$ , and $\\leq 0$ for odd $j$ . Moreover, $S_{n}=0$ (Principle of Inclusion-Exclusion).

Proof.

Let $Y=\\bigcup_{1\\leq i\\leq n}A_{i}$ .

	$\\displaystyle S_{j}$	$\\displaystyle=$	$\\displaystyle\\int_{Y}d\\mu+\\sum_{k=1}^{j}(-1)^{k}\\sum_{1\\leq i_{1}<i_{2}<\\ldots%<i_{k}\\leq n}\\int_{Y}\\chi_{A_{i_{1}}\\cap A_{i_{2}}\\cap\\ldots\\cap A_{i_{k}}}d\\mu$
		$\\displaystyle=$	$\\displaystyle\\int_{Y}d\\mu+\\sum_{k=1}^{j}(-1)^{k}\\int_{Y}(\\sum_{1\\leq i_{1}<i_{%2}<\\ldots<i_{k}\\leq n}\\chi_{A_{i_{1}}\\cap A_{i_{2}}\\cap\\ldots\\cap A_{i_{k}}})d\\mu$

By Lemma 2,

$\\displaystyle S_{j}$	$\\displaystyle=$	$\\displaystyle\\int_{Y}d\\mu+\\sum_{k=1}^{j}(-1)^{k}\\int_{Y}\\binom{\|I(x)\|}{k}d\\mu$
	$\\displaystyle=$	$\\displaystyle\\sum_{k=0}^{j}(-1)^{k}\\int_{Y}\\binom{\|I(x)\|}{k}d\\mu$
	$\\displaystyle=$	$\\displaystyle\\int_{Y}\\sum_{k=0}^{j}(-1)^{k}\\binom{\|I(x)\|}{k}d\\mu$

Since $|I(x)|>0$ for $x\\in Y$ , it follows from Corollary 1 that, in the last integral, the integrand is $\\geq 0$ for even $j$ and $\\leq 0$ for odd $j$ . Therefore the same is true for the integral itself. In addition, the integrand is identically 0 for $j=n$ , hence $S_{n}=0$ .∎

This proof shows that at the heart of Bonferroni’s inequalities lie similar inequalities governing the binomial coefficients.