Inclusion-Exclusion Principle for Three Sets

1.9k Views Asked by At

If $|A\cap B|= \varnothing $ (disjoint sets),

then $|A \cup B|=|A|+|B|$

Using this result alone, prove $|A\cup B| = |A| + |B| - |A\cap B|$

$|A\cup B| = |A| + |B - A|$

$|A\cap B| + |B - A| = |B|$,

summing gives

$|A\cup B| = |A| + |B| - |A\cap B|$.

In the same way, prove:

$$|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|$$


$|A∪B∪C| = |A|+|B-A|+|C-B-A|$

$|A∩B| + |B-A| = |B|$

$|C-A| + |A∩C| = |C|$

$|C-B|+|+|B∩C|=|C|$

$|C-B-A| + |C| = |C-A|+|C-B|+ |A∩B∩C|$

summing the previous five equations gives

$|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|$