principle of inclusion-exclusion, proof of
Now consider a collection of exactly two sets and . We know that
Furthermore, the three sets on the right-hand side of that equation must be disjoint. Therefore, by the addition principle, we have
So the principle of inclusion-exclusion holds for any two sets.
Now consider a collection of finite sets . We assume that the principle of inclusion-exclusion holds for any collection of sets where . Because the union of sets is associative, we may break up the union of all sets in the collection into a union of two sets:
By the principle of inclusion-exclusion for two sets, we have
Now, let be the collection of all -fold intersections of , and let be the collection of all -fold intersections of that include . Note that is included in every member of and in no member of , so the two sets do not duplicate one another.
We then have
by the principle of inclusion-exclusion for a collection of sets. Then, we may distribute set intersection over set union to find that
Note, however, that
Hence we may again apply the principle of inclusion-exclusion for sets, revealing that
The second sum does not include . Note, however, that , so we have
Combining the two sums yields the principle of inclusion-exclusion for sets.
|Title||principle of inclusion-exclusion, proof of|
|Date of creation||2013-03-22 12:33:27|
|Last modified on||2013-03-22 12:33:27|
|Last modified by||mps (409)|