Editing Inclusion–exclusion principle (section)

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