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.