Inclusion exclusion principle

a look at the inclusion-exclusion principle

1. Inclusion/Exclusion Principle
Tyler Murphy
April 30, 2014
This follows from the in-class work on 30 April 2014
Problem 1
LetAandBbe nite sets.
Prove that ifjA[Bj<jAj+jBj, thenA\B6=;
Proof.Directly.
By The inclusion/Exclusion Principle,jA[Bj=jAj+jBj jA\Bj.
Suppose thatjA[Bj<jAj+jBj.
Then, by I.E.P., we havejAj+jBj jA\Bj<jAj+jBj.
SubtractingjAj+jBjfrom both sides, we get -jA\Bj<0:
So,jA\Bj>0:
SoA\B6=;.
Problem 2
LetAandBbe nite sets in a universal setU.
Find a formula forjA[B
c
j:
By I.E.P.,jA[B
c
j=jAj+jB
c
j jA\B
c
j:
Now, we need to ask ourselves what each of these pieces involving the compliment is.
First consider whatB
c
is. That is everything inUthat is not inB. SojB
c
j=j
UBj=jUj jBj.
So now we havejA[B
c
j=jAj+jUj jBj jA\B
c
j:
Now we need to think about whatjA\B
c
jis. First, consider what this represents.
InjA[Bj=jAj+jBj jA\Bj, the last piece is the amount of stu we have
overcounted by.
1

2. So, ask yourself what we have overcounted by in this problem.
If we havejAj+jUj jBj, we counted all ofAonce when we counted itself and
again when we countedU. But when we took outB, we also took outA\B.
So in order to x this, we need to take out onejAjand add in onejA\Bj
So we havejA[B
c
j=jAj+jUj jBj jAj+jA\Bj:
This simplies tojUj jBj+jA\Bj.
So,jA[B
c
j=jUj jBj+jA\Bj.
So think about what we have said here. We have said thatjA\B
c
j=jAA\Bj.
Let's try to justify that. Consider whatA\B
c
is. It is everything inAAND everything
NOT inB. So this is all the things inA, but not in the intersection ofAandBbecause those
things are inB. So we have everything inAminus the things in both. SoA\B
c
=AA\B.
So it is ok to make our claim.
The idea with all of this is to think about what the I.E.P. means. It simply means
take all the things in the rst set, add it to all the things in the second set, and take out
everything you overcounted.
So if you ever get stuck with trying to gure out what the last piece of the I.E.P. looks
like, just step back and think about what you have overcounted.
2