Recitation 26

The inclusion-exclusion principle is a counting technique to obtain number of elements in the union or the complement of the union of several finite sets. To get an idea of what the principle is saying, it is good to take a look at the following special cases. For two finite sets and three finite sets, we have $\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|,$ and $\left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|B\cap C\right|-\left|C\cap A\right|+\left|A\cap B\cap C\right|.$