[SOLVED] Proving the rule of sum of sets.

**Kitizhi** · August 10th 2009, 12:54 PM

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

**Gamma** · August 10th 2009, 01:12 PM

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 $|A \cup B|=|A|+|B|-|A\cap B|=|A|+|B|-0=|A|+|B|$ .

Think you can take it from there?

**Kitizhi** · August 10th 2009, 01:17 PM

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

**Gamma** · August 10th 2009, 01:31 PM

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 $\{A,A_1,A_2,...,A_n\}$ we have $|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 $\{A,A_1,A_2,...,A_n,A_{n+1}\}$ are all disjoint. By induction hypothesis $|A\cup A_1 \cup A_2 \cup ... \cup A_{n}|=|A|+ |A_1| + |A_2| +... + |A_n|$ . Now we notice $(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

$|(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}|$ $=(|A|+ |A_1| + |A_2| +... + |A_n|)+|A_{n+1}|=|A|+ |A_1| + |A_2| +... + |A_n|+|A_{n+1}|$

Which completes the induction.

**Plato** · August 10th 2009, 01:36 PM

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: $\left| {\bigcup\limits_{k = 1}^N {E_k } } \right| = \sum\limits_{k = 1}^N {\left| {E_k } \right|}$ .

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

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

Now finish.

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

LinkBack

Thread Tools

Display

[SOLVED] Proving the rule of sum of sets.

Similar Math Help Forum Discussions

Proving Sets

Proving that A~B then B~A for infinite sets

Proving two sets are equal

Proving Sets

[SOLVED] I need help proving that the cross product of 2 countable sets is countable.

Search Tags