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|$


$|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.



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} $$

  • $\begingroup$ Can you explain the reasoning behind each step? $\endgroup$ – Vayelin Mar 29 '16 at 17:55
  • $\begingroup$ @Toon1334 please take a look at my answer now. $\endgroup$ – Saaqib Mahmood Mar 30 '16 at 2:45

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.