# Counting sets - Addition principle

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.

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

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