How inclusion-exclusion works demonstrated on an set example

Question

In the inclusion-exclusion set example:

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

we subtract $|A\cap B\cap C|$ three times because it is included in $|A\cap B|$,$|A\cap C|$ and $|B\cap C|$, but we are adding it back only once as $+|A\cap B\cap C|$. Why? Common sense says: we should add it back twice if we subtracted it three times.

Please explain using simple words :)

Answer 1

First we added $|A\cap B\cap C|$ three times because $A\cap B\cap C$ is a subset of $A$, $B$ and $C$.

Then we subtracted it again three times because $A\cap B\cap C$ is a subset of $A\cup B$, $A\cup C$ and $B\cup C$.

Then we add it once so that it present exactly one time, as it should.

Answer 2

Let us make an explicit case by case check for the possible of a choice of $x\in A\cup B\cup C$.

• If $x$ is in exactly one of the three sets, w.l.o.g. in $A$, then it is counted as follows: $1= (1+0+0)-(0+0+0)+0$.
• If $x$ is in exactly two of the three sets, w.l.o.g. in $A\cap B$, then it is counted as follows: $1= (1+1+0)-(1+0+0)+0$.
• If $x$ is in exactly three of the three sets, so in $A\cap B\cap C$, then it is counted as follows: $1= (1+1+1)-(1+1+1)+1$.

For each $x\in A\cup B\cup C$ we have the same contribution on both sides.

Euler diagrams may make things clear in a visual way.