Results 1 to 5 of 5

Math Help - [SOLVED] Proving the rule of sum of sets.

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    48

    [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|.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    48
    Quote Originally Posted by Gamma View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by Kitizhi View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Sets
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 8th 2011, 05:40 PM
  2. Proving that A~B then B~A for infinite sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 21st 2010, 11:11 AM
  3. Proving two sets are equal
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 22nd 2010, 10:21 AM
  4. Proving Sets
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: February 28th 2010, 02:22 AM
  5. Replies: 11
    Last Post: October 11th 2008, 07:49 PM

Search Tags


/mathhelpforum @mathhelpforum