Show that the number of elements in exactly one of three sets $A, B, C$ is given by $|A| + |B| + |C| - 2|A \cap B| + 3|A \cap B \cap C|$

1.7k Views Asked by At

I think we can show this for two sets $A$ and $B$ like this below.

Suppose $A$ contains $n$ elements and $B$ contains $m$ elements. Assume $A$ and $B$ share $k$ elements. Then $x = n - k$ elements only occur in $A$ and $y = m - k$ elements only occur in $B$. So the number we are after is $x + y = n - k + m - k = n + m - 2k = |A| + |B| - 2|A \cap B|.$

The situation for the three sets is shown below pictorially.

enter image description here

Removing $k$ twice lops off the overlapping part of $C$ twice so I see why we should add back $2|A \cap B \cap C|.$ But why do we add back one more $|A \cap B \cap C|?$ Thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

You can do this by an easy induction on the number of elements in $A\cup B\cup C$. When that is $0$ the result obviously holds. If not remove one element and assume the result for what remains; the element must be in one of the $7$ coloured areas and in each case the result easily follows from the induction. (Basically, show elements of the monochrome regions contribute $1$ to to expression and from the other regions $0$).

You can of course also give names to the numbers in each region (these give $7$ unknowns) and evaluate your expression in terms of those numbers, in which case it is just simple algebra.