A calculus of the absurd

Chapter 18 Further combinatorics

18.0.1 The principle of inclusion-exclusion

This is a useful method which allows us to write the magnitude of the union of sets in terms of the magnitude of individual sets and their intersection. Often it is a lot easier to work with set intersections than it is to work with set unions, so this method is very powerful as a result.

Let us suppose that we have two sets, \(A\) and \(B\). In this case we would like to find a different way to write \(|A \cup B|\), one which does not involve a union. One thing which can really help here is to draw a diagram and effectively apply some geometry.

(-tikz- diagram)

What we are interested in finding is the area of the entire diagram. Clearly we would like to add the area of \(|A|\) and the area of \(|B|\), but the problem is that if we guess that the total area is \(|A| + |B|\), then we will have also counted the contents of \(|A \cap B|\) twice - which is easily remedied by subtracting it. By this informal line of argument we get that

\begin{align} |A \cup B| = |A| + |B| - |A \cap B| \end{align}

the c