Inclusion-exclusion principle

The inclusion-exclusion principle is a theorem of set theory relating to the cardinality of a set defined as the union (mathematics) of a finite, or at most countable, collection of sets. The general form of the theorem for a collection ${A_{1},\cdots ,A_{n}}$ is $|A_{1}\cup \cdots \cup A_{n}|=\sum _{1\leq i\leq n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}|A_{1}\cap \cdots \cap A_{n}|$. This may be explained intuitively by stating that if we simply take as the cardinality of the union the sum of the cardinalities of the constituent sets, then we have counted those elements that lie in more than one of those sets more than once, so we subtract the sum of the cardinalities of two-way intersections. However, now we have subtracted those elements contained in three or more sets too many times, so we have to add back the sum of the three-way intersections. This creates an overcount once again, and so we continue, alternating sign as we go, until we reach the intersection of all of the sets in the collection. In the case of a countably infinite collection of sets, we never actually reach this final stage; rather, it is a limiting case.