Suppose that you have two finite sets A and 
You can find the size of their union using
because when you work out |A| + |B| the elements of
are being `counted twice'. You compensate for this
by subtracting 
Now suppose you have three finite sets. A very careful analysis of counting will show you that
What is going on here is that you first try |A| + |B| + |C|
but this is wrong because elements in 
, 
, and
have been counted too much. You therefore try to eliminate
this over-counting by subtracting 
but then notice that elements of 
have been `over removed'.
You compensate for this by adding 
and all is well.
We are edging toward the inclusion-exclusion enumeration principle.
Let is look at a concrete example.
Let 
and 
Now (2) says
7 = 4 + 4 + 6 - 2 -3 -4 + 2, which happily is true.
We prove validity of the Inclusion-Exclusion counting principle.
Theorem Suppose 
and 
is a finite set
for 
It follows that
Proof
Induct on
If all 
are empty, then the theorem holds, and
the induction starts without difficulty. Now focus on the case where
Pick any 
and form new sets
by 
(i.e. remove x from all the sets
which contain it). Now 
so the theorem holds for the sets 
by induction. Now pop
x back in to all sets from which you deleted it.
The re-insertion of x makes a contribution
of +1 on the left hand side.
On the right, suppose x occurs in
exactly 
of the 
. The re-insertion of x has the
effect of adding
exactly 
to the right hand side.
However, we have prepared the ground in the previous section,
so we know that this quantity is 1. The induction step is complete, and thus
the inclusion-exclusion principle is valid.
