# Counting AUB

• Mar 27th 2011, 08:54 AM
qwerty10
Counting AUB
How to prove lAUBl=lAl+lBl-lAnBl via a counting arguement. A,B finite sets

Can we simply argue:In counting the elements of AUB, we count the elements in A,nA and the elements in B, nB. But in couting the elements of A and elements of B we have counted x elements twice since the sets intersect. Therefore, we subtract the duplicate, AnB. Then because A,B are finite sets, AnB and AUB are finite sets.

I feel like this isn't a very strong proof. Is there a more rigorous way of proving the result?
• Mar 27th 2011, 09:03 AM
Plato
Quote:

Originally Posted by qwerty10
How to prove lAUBl=lAl+lBl-lAnBl via a counting arguement. A,B finite sets
Can we simply argue:In counting the elements of AUB, we count the elements in A,nA and the elements in B, nB. But in couting the elements of A and elements of B we have counted x elements twice since the sets intersect. Therefore, we subtract the duplicate, AnB. Then because A,B are finite sets, AnB and AUB are finite sets.

That is essentially correct.
Any element in \$\displaystyle A\cap B\$ is counted once when counting
\$\displaystyle A\$ then again when when counting \$\displaystyle B\$.
The subtraction removes the over-count.
• Mar 27th 2011, 09:09 AM
qwerty10
Thanks
Would this be a sufficient enough reasoning when proving the base case n=2 of the inclusion-exclusion principle?
• Mar 27th 2011, 09:13 AM
Plato
Yes.