1

I need help proving Prove $|A_1\cup\dotsb\cup A_n|\leq|A_1|+|A_2|+\dotsb+|A_n|$ (probably using induction. I have already proven that $|A_1\cup A_2|\leq|A_1|+|A_2|$

by

$|A_1\cup A_2|= (|A_1|+|A_2|)-|A_1\cap A_2|$ & Def of union of sets
$-|A_1\cap A_2|=|A_1\cup A_2|-(|A_1|+|A_2|)$ & Addition is well-defined
$|A_1\cap A_2|\geq 0$ & Def of sets (cant have neg num of elements)
$-|A_1\cap A_2|\leq 0$ & Multiplication is well defined
$|A_1\cup A_2|-(|A_1|+|A_2|)=-|A_1\cap A_2|\leq 0$ & Def of $\leq$
$|A_1\cup A_2|-(|A_1|+|A_2|)\leq 0$ & Def of $\leq$
Thus $|A_1\cup A_2|\leq|A_1|+|A_2|$ is true & Addition is well-defined

Please explain each step because I really want to understand what/why those steps are used.

Thanks

Vayelin
  • 25

1 Answers1

2

We have the result: $$\left\vert A_1 \cup A_2 \right\vert \leq \left\vert A_1 \right\vert + \left\vert A_2 \right\vert.$$

Now suppose that $$\left\vert \bigcup_{i=1}^n A_i \right\vert \leq \sum_{i=1}^n \left\vert A_i \right\vert,$$ where $n$ is a natural number.

Then we have $$ \begin{align} \left\vert \bigcup_{i=1}^{n+1} A_i \right\vert &= \left\vert \left( \bigcup_{i=1}^n A_i \right) \cup A_{n+1} \right\vert \ \mbox{ using the associative property of the union of sets } \\ &\leq \left\vert \bigcup_{i=1}^n A_i \right\vert + \left\vert A_{n+1} \right\vert \\ & \ \ \ \mbox{ using the result for union of two sets, where the first set is a union of $n$ sets} \\ &\leq \sum_{i=1}^n \left\vert A_i \right\vert + \left\vert A_{n+1} \right\vert \ \mbox{ using our induction hypothesis } \\ &= \sum_{i=1}^{n+1} \left\vert A_i \right\vert . \end{align} $$

Saaqib Mahmood
  • 26,762