Let $A_i, A_2, ..., A_n$ be finite sets and let $A = A_1 \cup A_2 \cup...\cup A_n$. prove:

$$ |A| \leq\ \sum_{i=1}^n |A_i|-(n-1)|A_1 \cap A_2 \cap...\cap A_n| $$

Thanks for any tips/proof! Been struggling on this one for a while!

  • $\begingroup$ How about using exclusion-inclusion principle $\endgroup$ – Ashar Tafhim Nov 13 '16 at 11:25
  • 1
    $\begingroup$ Suppose you have an element $x \in A$. How many times do you count it on the left hand side? And at least how many times on the right hand side (separate the different cases)? $\endgroup$ – ToucanNapoleon Nov 13 '16 at 11:27

Observe that $$ A = A_1 \cup (A_2 - A_1) \cup (A_3 - (A_1 \cup A_2) \cup \cdots $$ in which $A_1,\ A_2 - A_1,\ A_3 - (A_1 \cup A_2),\ \cdots\ $ are disjoint. Therefore, \begin{align} A &= |A_1| + |A_2 - A_1| + |A_3 - (A_1 \cup A_2)| + \cdots \\ & \leq |A_1| + (|A_2| - |A_1 \cap A_2|) + (|A_3| - |A_1 \cap A_2 \cap A_3|) + \cdots \\ & \leq |A_1| + (|A_2| - |A_1 \cap \cdots \cap A_n|) + (|A_3| - |A_1 \cap \cdots \cap A_n|) + \cdots \\ &= \sum_{i=1}^n |A_i| - (n-1)|A_1 \cap A_2 \cap \cdots \cap A_n| \end{align}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.