PROFESSOR: The arguments that we just reviewed for proving inclusion-exclusion by looking at how many times points are counted can be made perfectly rigorous. In fact, we'll do that in a later segment, but it's interesting and good practice to realize that they can also be proved just from some simple set theoretic identities using the ordinary disjoint sum rule.
So how am I going to prove the inclusion-exclusion principle for two sets? The size of A union B is the size of A plus the size of B minus the size of A intersect B, and the idea is just break up A union B into disjoint sets because once they're disjoint sets, I can add up their sizes.
So if we look at A union B, A union B can be expressed as the union of two disjoint sets, namely A-- the round blue circle-- and what's left-- the points in B that are not in A, so this lighter orange-colored region. So A and B union and B minus A-- so these are the points in A and these are the points that are in B that are not in A are two disjoint sets whose union is A union B.
That means that I know the size of this. It's just the size of A plus the size of B minus A because they're disjoint, so we conclude by the sum rule that the size of A union B is equal to the size of A plus the size of B minus A.
So now I need a little lemma that says that the size of B minus A is the size of B minus the size of A intersection B. If I get that, then I've proved inclusion-exclusion because now I have A plus B minus A intersection B. So we need a lemma.
The lemma says that the size of B minus A is equal to the size of B minus the size of A intersect B. So here we're back to the Venn diagram. A is blue, B is reddish, and the intersection region, that lens-shaped region, is shown in purple, and we want to prove this lemma.
Well, again, what we can do is look at the set B broken up into two pieces. B can be expressed as a disjoint union of the part of B that's in A union, the part of B that's not in A. That is, for any set B and any set A, B is equal to the B points that are in the A and the B points that are not in A covers all the cases. And this, again, is a disjoint union.
So we conclude immediately from the sum rule that the size of B is equal to the size of B intersection A plus the size of B minus A. And then just transposing this term for the size of B minus A to the left-hand side of the equality, I've proven the lemma and we're done.
Now, inclusion-exclusion for three sets, we've said before it's this slightly more complicated thing where you've got a sum of the intersections of one set minus the sizes of the intersections of two sets plus the size of the intersection of three sets. And that generalizes to the following somewhat messy formula, but let's look at it closely together.
If I want to know what's the size of A1 through An-- if I have n sets potentially overlapping A1 A2 through An and I want their union, and I can express the union of them in terms of a sum of sizes of intersections, and here's the formula. Let's read this slowly together.
So this is a sum over every possible subset of the indices 1 through n that's not empty. So this sum is ranging over S, and it can do it in any order. It's typical to write the sum where you sum up first all the sets S of size 1 and then sum up all the sets S of size 2 and sum-- but that's not necessary.
We just sum in any order for every subset of the indices, the size of the intersection of the Ai's that are in this set of indices specified by S. So this is just the intersection of those A's that s specifies.
Now, what's the sign of that size of intersection? As we said, if it's of odd size, I want it to count positively. So if I take minus 1 to the odd size plus 1, I get an even power of minus 1, so it comes out to be 1.
If, on the other hand, the size of S is even-- so I'm taking an intersection of an even number of sets-- then this number to the plus 1 is odd. I'm taking minus 1 to an odd power, and sure enough, I'm getting the negative sign on all the intersections of odd size. So that's what this rather concise but hairy formula looks like.
Here we have an intersection over the Ai's where the i is specified by the set S of indices, and I sum up these terms over every possible nonempty set S. That is the generalized form of inclusion-exclusion for n sets.
Now, how do we prove this? Well, there's lots of ways to prove it. The simplest way is to do it actually by induction. It's not very hard to do by induction. You just use the two-set version of inclusion-exclusion, which we've proved rigorously using the disjoint sum rule, and you go from the union of the first n sets plus the nth and apply the formula and simplify, and that works fine.
The other problem with it is [? it's ?] not really very informative. You prove the theorem all right. As is frequently the case with induction proofs, you have the right induction hypothesis, the proof is kind of mechanical, but you don't really learn much from it-- not always, but in this case, I don't think you do.
A second way to do it is by using the binomial theorem and counting. This is a way to make rigorous the argument that said, OK, we counted two points in the intersection of two things twice, so we had to subtract them away, and then that meant that we were not counting the things that were in the intersection of three not at all, and so on. And we've talked through that argument informally, and I will do that in a next segment of making that argument a little bit more precise to prove the general theorem.
And--
[AUDIO OUT]
Law from algebra, we can just look at a product of sums and understand how it expands into a sum of products by the distributivity law. And that's worked out in a problem that is in the text, and I'm not going to do that in a video.