Editing Inclusion–exclusion principle (section)

==Proof of main statement==

Choose an element contained in the union of all sets and let <math>A_1, A_2, \dots, A_t</math> be the individual sets containing it. (Note that ''t'' &gt; 0.) Since the element is counted precisely once by the left-hand side of equation ({{EquationNote|1}}), we need to show that it is counted precisely once by the right-hand side. On the right-hand side, the only non-zero contributions occur when all the subsets in a particular term contain the chosen element, that is, all the subsets are selected from <math>A_1, A_2, \dots, A_t</math>. The contribution is one for each of these sets (plus or minus depending on the term) and therefore is just the (signed) number of these subsets used in the term. We then have: 

:<math>\begin{align}
|\{A_i \mid 1 \leqslant i \leqslant t\}| &- |\{A_i \cap A_j \mid 1 \leqslant i < j \leqslant t\}| + \cdots + (-1)^{t+1}|\{A_1 \cap A_2 \cap \cdots \cap A_t\}| = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t}.
\end{align}</math>

By the [[binomial theorem]],

:<math> 0 = (1-1)^t= \binom{t}{0} - \binom{t}{1} + \binom{t}{2} - \cdots + (-1)^t\binom{t}{t}.</math>

Using the fact that <math>\binom{t}{0} = 1</math> and rearranging terms, we have

:<math>1 = \binom{t}{1} - \binom{t}{2} + \cdots + (-1)^{t+1}\binom{t}{t},</math>

and so, the chosen element is counted only once by the right-hand side of equation ({{EquationNote|1}}).

===Algebraic proof===
An algebraic proof can be obtained using [[indicator function]]s (also known as characteristic functions). The indicator function of a subset ''S'' of a set ''X'' is the function 

:<math>\begin{align}
&\mathbf{1}_S: X \to \{0,1\} \\
&\mathbf{1}_S(x) = \begin{cases} 1 & x \in S\\ 0 & x \notin S \end{cases}
\end{align}</math>

If <math>A</math> and <math>B</math> are two subsets of <math>X</math>, then 

:<math>\mathbf{1}_A \cdot\mathbf{1}_B = \mathbf{1}_{A\cap B}.</math>

Let ''A'' denote the union <math display="inline">\bigcup_{i=1}^n A_i</math> of the sets ''A''<sub>1</sub>, ..., ''A<sub>n</sub>''. To prove the inclusion–exclusion principle in general, we first verify the identity

{{NumBlk|:|<math>\mathbf{1}_A  =\sum_{k=1}^n (-1)^{k-1} \sum_{I\subset\{1,\ldots,n\} \atop|I| = k} \mathbf{1}_{A_I}</math>|{{EquationRef|4}}}}

for indicator functions, where:

:<math>A_I = \bigcap_{i\in I} A_i.</math>

The following function

:<math>\left (\mathbf{1}_A-\mathbf{1}_{A_1} \right )\left (\mathbf{1}_A-\mathbf{1}_{A_2} \right )\cdots \left (\mathbf{1}_A-\mathbf{1}_{A_n} \right )=0,</math>

is identically zero because: if ''x'' is not in ''A'', then all factors are 0−0 = 0; and otherwise, if ''x'' does belong to some ''A<sub>m</sub>'', then the corresponding ''m''<sup>th</sup> factor is 1−1=0. By expanding the product on the left-hand side, equation ({{EquationNote|4}}) follows.

To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation ({{EquationNote|4}}) over all ''x'' in the union of ''A''<sub>1</sub>, ..., ''A<sub>n</sub>''. To derive the version used in probability, take the [[expected value|expectation]] in ({{EquationNote|4}}). In general, [[Lebesgue integral|integrate]] the equation ({{EquationNote|4}}) with respect to&nbsp;''μ''. Always use linearity in these derivations.