# Thread: [SOLVED] Proving the rule of sum of sets.

1. ## [SOLVED] Proving the rule of sum of sets.

Can someone help me with this proof please.

Let n be a positive integer. If A1, A2, ... , An are pairwise disjoint finite sets then | A1 U A2 U ... U An| = |A1| + |A2| + ... + |An|.

2. I would use induction to make matters simple. This way you only need to do it for two disjoint sets.

Let A and B be disjoint finite sets. Then $\displaystyle |A \cup B|=|A|+|B|-|A\cap B|=|A|+|B|-0=|A|+|B|$.

Think you can take it from there?

3. Originally Posted by Gamma
I would use induction to make matters simple. This way you only need to do it for two disjoint sets.

Let A and B be disjoint finite sets. Then $\displaystyle |A \cup B|=|A|+|B|-|A\cap B|=|A|+|B|-0=|A|+|B|$.

Think you can take it from there?
Yeah I did realize that you would need to use induction.

Hmm..can you go a little further then that please? I kinda did notice that but I was kinda stuck to go take it further.

4. Yeah sure. So we proved about the base case when you adjoin 1 disjoint set to A that is how you count them.

So suppose for induction hypothesis that for disjoint sets $\displaystyle \{A,A_1,A_2,...,A_n\}$ we have $\displaystyle |A\cup A_1 \cup A_2 \cup ... \cup A_{n}|=|A|+ |A_1| + |A_2| +... + |A_n|$, we now show it must be true for adjoining n+1 disjoint sets. So $\displaystyle \{A,A_1,A_2,...,A_n,A_{n+1}\}$ are all disjoint. By induction hypothesis $\displaystyle |A\cup A_1 \cup A_2 \cup ... \cup A_{n}|=|A|+ |A_1| + |A_2| +... + |A_n|$. Now we notice $\displaystyle (A\cup A_1 \cup A_2 \cup ... \cup A_{n})\cap A_{n+1}=\emptyset$ so by our base case in the first post

$\displaystyle |(A\cup A_1 \cup A_2 \cup ... \cup A_{n}) \cup A_{n+1}|=|A\cup A_1 \cup A_2 \cup ... \cup A_{n}|+|A_{n+1}|$$\displaystyle =(|A|+ |A_1| + |A_2| +... + |A_n|)+|A_{n+1}|=|A|+ |A_1| + |A_2| +... + |A_n|+|A_{n+1}|$

Which completes the induction.

5. Originally Posted by Kitizhi
Yeah I did realize that you would need to use induction.
Hmm..can you go a little further then that please? I kinda did notice that but I was kinda stuck to go take it further.
Assume the Nth case is true: $\displaystyle \left| {\bigcup\limits_{k = 1}^N {E_k } } \right| = \sum\limits_{k = 1}^N {\left| {E_k } \right|}$.

Then let $\displaystyle E = \bigcup\limits_{k = 1}^N {E_k } \;\& \,E \cap E_{N + 1} = \emptyset$.

By the base case we know that $\displaystyle \left| {E \cup E_{N + 1} } \right| = \left| E \right| + \left| {E_{N + 1} } \right|$.

Now finish.