Vtyjkyuk

Let A, B, and C be finite sets. Prove or disprove:

If $|A cup B cup C | = |A| + |B| + |C|$, then $A, B$, and $C$ must be pairwise disjoint.

I started with inclusion-exclusion formula

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

Hypothesis says if $|A cup B cup C | = |A| + |B| + |C|$, then expression $|A cap B cap C| - |A cap B| - |A cap C| - |B cap C| $, must be equal to zero. So, we have

$$ |A cap B cap C| - |A cap B| - |A cap C| - |B cap C| = 0$$
$$ |A cap B cap C| = |A cap B| + |A cap C| + |B cap C| tag1$$

Now, I am not sure how finish this proof. I found two ways, but I do not know if are correct.

First way

If $x in |A cap B cap C|$, then $x in |A cap B| wedge xin |A cap C| wedge x in |B cap C|$.

So if we count the cardinality of $|A cap B cap C| = |A cap B| + |A cap C| + |B cap C|$, then if $x in |A cap B cap C|$ then $x$ is counted once but on RHS $x$ is counted three times. Thus the equation is true if $A = B = C = emptyset$.

Therefore $A, B,$ and $C$ are pairwise disjoint.

Second way

From inclusion-exclusion formula, I know $$|A cap B cap C| = - |A| - |B| - |C| + |A cap B| + |A cap C| + |B cap C| - |A cup B cup C |$$
I substitute in equation (1)
$$ -|A| - |B| - |C| + |A cap B| + |A cap C| + |B cap C| - |A cup B cup C | = |A cap B| + |A cap C| + |B cap C|$$
The expression $|A cap B| + |A cap C| + |B cap C|$ cancels out.
$$ |A| + |B| + |C| + |A cup B cup C | = 0$$

And this equation is true if $A = B = C = emptyset$.

Therefore $A, B,$ and $C$ are pairwise disjoint.

My question is which way is correct and better or if there is a different method to prove the proposition. Thank you. (I am self-studying student, who is reading a textbook about discrete mathematics).

• Your first way is correct unless $A cap B cap C=emptyset.$


• The equation in your second way has to be corrected as $$|A cap B cap C| = - |A| - |B| - |C| + |A cap B| + |A cap C| + |B cap C| + |A cup B cup C |$$ and substituting this leads to a nothing (as you use the same equation twice).

This is how I would answer this question (using inclusion-exclusion principal):

$A cap B cap Csubset A cap B$ and therefore $|A cap B cap C| le |A cap B|, |A cap C|, |B cap C|.$

Then we have
$$3|A cap B cap C| le |A cap B| + |A cap C| + |B cap C|.$$ Now combining this with what you have already found $$|A cap B cap C| = |A cap B| + |A cap C| + |B cap C|,$$ we can say $$|A cap B| =|A cap C| = |B cap C|=|A cap B cap C|=0 .$$

Suppose $A$, $B$, $C$ are not pairwise disjoint. Then the intersection of two of them, wlog $A$ and $B$, is nonempty. Now $|A cup B| = |A| + |B| - |A cap B| < |A| + |B|$,
and $|A cup B cup C| le |A cup B| + |C| < |A| + |B| + |C|$.