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, AA and BB. In this case we would like to find a different way to write |AB||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||A| and the area of |B||B|, but the problem is that if we guess that the total area is |A|+|B||A|+|B|, then we will have also counted the contents of |AB||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

|AB|=|A|+|B||AB|\displaystyle|A\cup B|=|A|+|B|-|A\cap B| (21.1)