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

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 can obtain the very useful result that