Inclusion–exclusion principle
Algebraic proof

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

If A {\displaystyle A} and B {\displaystyle B} are two subsets of X {\displaystyle X}, then

Let A denote the union ⋃ i = 1 n A i {\textstyle \bigcup _{i=1}^{n}A_{i}} of the sets A,..., A. To prove the inclusion–exclusion principle in general, we first verify the identity

for indicator functions, where:

The following function

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, then the corresponding m factor is 1−1=0. By expanding the product on the left-hand side, equation (4) follows.

To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation (4) over all x in the union of A,..., A. To derive the version used in probability, take the expectation in (4). In general, integrate the equation (4) with respect to μ. Always use linearity in these derivations.
oulipo:avoid_letter[a]