0
$\begingroup$

Theorem: If A and B are non-empty sets, and A and B are disjoint, then $$ |A \bigcup B| = |A|+|B|$$ If I have n sets and all of them are disjoint, then $ |A_1 \bigcup A_2 \bigcup...\bigcup A_n| = |A_1|+|A_2|+...+|A_n|$

If I want to prove that, can I do like this?

1) By the theorem we know that is it true fpr n=2

2) we suppose that it is $ A_1, A_2, ... , A_k $ is disjoint then $$ |A_1 \bigcup A_2 \bigcup...\bigcup A_k| = |A_1|+|A_2|+...+|A_k|$$

3) we suppose that $ A_1, A_2, ... , A_k, A_{k+1} $ is disjoint sets, then it follows that $A_1 \bigcup A_2 \bigcup...\bigcup A_k$ and $A_{k+1}$ are disjoint sets. The theorem above then applies that $$ |A_1 \bigcup A_2 \bigcup...\bigcup A_k\bigcup A_{k+1}| = |A_1|+|A_2|+...+|A_k|+|A_{k+1}|$$ and by 2) $$ |A_1 \bigcup A_2 \bigcup...\bigcup A_k| = |A_1|+|A_2|+...+|A_k|$$ so $$ |A_1 \bigcup A_2 \bigcup...\bigcup A_k\bigcup A_{k+1}| = |A_1|+|A_2|+...+|A_k|+|A_{k+1}|$$ The result follows now from induction principle.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

What you have is fine. I've tidied it up a little, exploiting the $\bigcup$ notation a little more here:

Theorem: If $A$ and $B$ are non-empty sets, and $A$ and $B$ are disjoint, then $$ \left\vert A \cup B\right\vert = |A|+|B|$$

Proposition: If we have $n$ pairwise disjoint sets, then $ \left\vert\bigcup_{j=1}^{n} A_j\right\vert = \sum_{j=1}^{n}|A_j|$

Proof of Proposition:

The case of $n=1$ is trivial.

Base Case: By the theorem we know that the proposition holds for $n=2$

Induction hypothesis: Assume that for some $k$, whenever $ A_1, A_2, \ldots, A_k $ are disjoint then $$ \left\vert\bigcup_{j=1}^{k} A_j\right\vert = \sum_{j=1}^{k}|A_j|$$

We now suppose that $ A_1, A_2, \ldots , A_k, A_{k+1} $ are pairwise disjoint. It follows that $\bigcup_{j=1}^{k}A_j$ and $A_{k+1}$ are disjoint sets. The Theorem tells us that $$ \left|\bigcup_{j=1}^{k+1} A_j\right| = \left\vert \left(\bigcup_{j=1}^{k} A_{j}\right) \cup A_{k+1}\right\vert= \left\vert \bigcup_{j=1}^{k} A_{j} \right\vert + \left\vert A_{k+1}\right\vert.$$

Now applying the induction hypothesis to this, we get $$\left|\bigcup_{j=1}^{k+1} A_j\right|=\left(\sum_{j=1}^{k}|A_j|\right)+|A_{k+1}|=\sum_{j=1}^{k+1}\vert A_{j}\vert$$ concluding our proof.


I've tried to follow your reasoning as closely as I could here. It is actually possible to be slightly more efficient. The base case really should be $n=1$. The proof for $n=2$ follows from this base case and the argument for the inductive step (which is really just an invocation of the Theorem).

$\endgroup$
3
  • $\begingroup$ I originally included this version as an edit, but it is more appropriate here. Sorry about any confusion. $\endgroup$
    – Unwisdom
    Apr 26, 2014 at 17:37
  • 1
    $\begingroup$ The very first indexed union symbol has a typo in the lower index, it says $n=j$ instead of $j=1$. $\endgroup$
    – Asaf Karagila
    Apr 26, 2014 at 17:58
  • $\begingroup$ @AsafKaragila - Thanks - I have made the correction. $\endgroup$
    – Unwisdom
    Apr 26, 2014 at 18:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .