Check proof that $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$

Question

Just trying to learn how inclusion-exclusion proofs work.

Do the inclusion-exclusion arguments work like that below? If not, what are my mistakes?

Suppose $x \in A.$ Then the expression above counts it once in $|A|$, removes it twice in $|A \cap B|, |A \cap C|$, then adds it back in $|A \cap B \cap C|: 1 - 2 + 1 = 0.$ The element in $A$ contributes nothing to the expression. The same analysis holds for elements in $B, C.$

Suppose $y \in A \cup B.$ Then $y \in A$ or $y \in B.$ So then the expression above counts it once in $|A|$ and once in $|B|$, removes it thrice in $|A \cap B|, |B \cap C|, |A \cap C|$, then adds it back in $|A \cap B \cap C|: 2 - 3 + 1 = 0.$ The element in $A \cap B$ contributes nothing to the expression. The same analysis holds for elements in $A \cup B, A\cup C, B \cup C.$

Suppose $z \in A \cup B \cup C.$ Then $z \in A$ or $z \in B$ or $z \in C.$ Thus the expression counts it once in $|A|$, once in $|B|$ and once in $|C|$, removes it thrice in $|A \cap B|, |B \cap C|, |A \cap C|$, then adds it back in $|A \cap B \cap C|: 3 - 3 + 1 = 1.$ So the element in $A \cap B \cap C$ is counted once by the expression.

Edit:

The proof as worked by T. Gunn, amWhy and mTur11 is as follows (just in case someone else sees it in the future and gets confused by the wrong proof):

Call $|A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$ $E$ for Expression.

We have three cases:

• $x \in A$ but not $B$ or $C.$ Then $E$ counts it once in $|A|$. The element in $A$ contributes $1$ to $E$. The same analysis holds for elements in $B, C.$
• $x \in A$ and $x \in B$ but $x \notin C.$ So then $E$ counts it once in $|A|$ and once in $|B|$, removes it once in $|A \cap B|: 2 - 1 = 1.$ The element in $A \cap B$ contributes $1$ to $E$. The same analysis holds for elements in $A \cap C, B \cap C.$
• $x \in A$ and $B$ and $C.$ Thus $E$ counts it once in $|A|$, once in $|B|$ and once in $|C|$, removes it thrice in $|A \cap B|, |B \cap C|, |A \cap C|$, then adds it back in $|A \cap B \cap C|: 3 - 3 + 1 = 1.$ So the element in $A \cap B \cap C$ is counted once by $E$.

Thus $E$ counts every element in $A \cup B \cup C$ once.

Answer 1

It depends on how many of $A, B, C$ the element is in.

• If $x \in A$ but not $B$ or $C$ then $x$ is counted once in the term $|A|$

• If $x \in A$ and $x \in B$ but $x \notin C$ then $|A| + |B| - |A \cap B|$ counts $x$ once

• If $x \in A$ and $B$ and $C$ then the whole right hand side counts $x$ once

And since we can permute the letters without effect, this characterizes all possibilities.

---

You can also bootstrap this from the identity $|A \cup B| = |A| + |B| - |A \cap B|$ because then

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

and hence

$$ |A \cup B \cup C| = |A| + (|B| + |C| - |B \cap C|) - (|A \cap B| + |A \cap C| - |A \cap B \cap C|). $$

Answer 2

You have not succeeded in your proof that

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

For an example of where your reasoning fails,

Suppose, with respect to your first supposition and what you claim follows review this counterexample to your reasoning:

Let $$A = \{1, 2\}, B=\{3, 4\}, C=\{4, 5\}. $$ Then

$|A\cup B \cup C| = |\{1, 2, 3, 4, 5\}| = 5$,

$|A| + |B|+ |C| = |\{1,2\} | + |\{3, 4\}| + |\{4, 5\}|= 6, \;$

$ |A\cap B| = |\{1, 2\}\cap \{3, 4\}| = 0, \;$

$ |A\cap C| = 0,\;$

$ |B\cap C| = 1,\;$ and

$|A\cap B \cap C| = 0$.

Then we have that (finding the cardinality of each side of the equation), that

$$ 5 = 6-1$$ which is true. But note that for $1,2, in A$, each is counted once on each side of the equation. This is a case in which the cardinality of $A$, that is $2$, contributes $2$ to the number of elements on each side of your equation. So your first supposition is incorrect. You are wrong to conclude for all sets A, described in your equation, that $|A|$ contributes nothing.

I think what may have sidetracked you is in mistaking $X \cup Y$ , vs. $X\cap Y$, (union versus intersection of two or more set, say $X, Y$. It is true that $$x \in A \rightarrow x \in A\cup B$$

But it not generally true that $x \in A \to x\in A\cap B$.

We can see the counterexample above, where $A\cup B = \{1, 2, 3, 4\}, $, but $A\cap B = \varnothing$. So yes, $x\in \{1, 2\} \to x\in \{1, 2, 3, 4\}$. Whereas $x \in \{1, 2\} \not\to x\in \varnothing$.

See also the following two counterexamples to your arguments:

---

If all the sets, $A, B, C$ are pairwise disjoint, (say, $A= \{1\}, B=\{2\}, C = \{3\}),$ we know that

$A\cap B = \varnothing, A\cap C = \varnothing,$ and $B\cap C = \varnothing$. (So clearly, $A\cap B \cap C=\varnothing$),

then it turns out that $|A\cup B \cup C| = |\{1, 2, 3\}| = |A|+ |B| +|C|.$

---

The other extreme case is when, say, $A=B=C$, e.g. $A=B=C = \{1\}$. Then $|A\cup B\cup C|= |\{1\}| = 1.$,

and $|A|+ |B| + |C| = 3$

and $|A\cap B| = |A\cap B| = |B\cap C| = |\{1\}| = 1$,

and $|A\cap B\cap C| = |\{1\}| = 1$.

So, using the formula you provide: We have $1 = 3 -(1+1+1)+ 1 \iff 1=1$, hence true.