Results 1 to 13 of 13

Math Help - Prove Cardinality of the sets

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Prove Cardinality of the sets

    Show that if A, B, and C are sets, then \left|{A \cup B \cup C}\right|= \left|{A}\right| + \left|{B}\right| + \left|{C}\right| - \left|{A \cap B}\right| - \left|{A \cap C}\right| - \left|{B \cap C}\right| + \left|{A \cap B \cap C}\right|.

    So i know that \left|{A \cup B}\right| = \left|{A}\right| + \left|{B}\right| - \left|{A \cap B}\right|. But i have no idea how to get to that final form
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bfpri View Post
    Show that if A, B, and C are sets, then \left|{A \cup B \cup C}\right|= \left|{A}\right| + \left|{B}\right| + \left|{C}\right| - \left|{A \cap B}\right| - \left|{A \cap C}\right| - \left|{B \cap C}\right| + \left|{A \cap B \cap C}\right|.

    So i know that \left|{A \cup B}\right| = \left|{A}\right| + \left|{B}\right| - \left|{A \cap B}\right|. But i have no idea how to get to that final form
    Inclusion exclusion principle?

    Or \text{card}A\cup B\cup C=\text{card }A\cup\left(B\cup C\right)=\text{card }A+\text{card }B\cup C-\text{card }A\cap (B\cup C). Go from there?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    \left|{A \cup B \cup C}\right|= \left|{A}\right| + \left|{B \cup C}\right| - \left|{A \cap (B \cup c)}\right|
    = \left|{A}\right| + \left|{B }\right| + \left|{C}\right| - \left|{B \cap C }\right|- \left|{A \cap (B \cup C) }\right|
    = \left|{A}\right| + \left|{B }\right| + \left|{C}\right| - \left|{B \cap C }\right|- \left|{(A \cap B) \cup (A \cap C) }\right|
    = \left|{A}\right| + \left|{B }\right| + \left|{C}\right| - \left|{B \cap C }\right|-( \left|{A \cap B}\right| + \left|{A \cap C}\right|- \left|{A \cap B \cup (A \cap C)}\right|)

    I think there is a parenthesis on the second half of the last line right? so that it distributes and makes \left|{A \cap B \cup (A \cap C)}\right| positive? Then I know \left|{A \cap B \cup (A \cap C)}\right| is equal to \left|{A \cap B \cap C}\right| But i'm not sure how to prove it..

    thanks for the help
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bfpri View Post
    Then I know \left|{A \cap B \cup (A \cap C)}\right| is equal to \left|{A \cap B \cap C}\right| But i'm not sure how to prove it..

    thanks for the help
    Do you know the distributive laws of union/intersection?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by Drexel28 View Post
    Do you know the distributive laws of union/intersection?
    Yes, but I'm not sure how to apply it to that.. btw i left out a parenthesis..it should be \left|{(A \cap B) \cup (A \cap C)}\right|. For the distributive laws i know that A \cup (B \cap C)= (A \cup B) \cap (A \cup C). Is that what you're talking about?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bfpri View Post
    For the distributive laws i know that A \cup (B \cap C)= (A \cup B) \cap (A \cup C). Is that what you're talking about?
    Indeed, obviously. But, you can do this for any set (intersection of sets, union of sets, etc.). Particularly, \left(A\cap B\right)\cup\left(A\cap C\right)=\left(A\cup\left(A\cap C\right)\right)\cap\left(B\cup\left(A\cap C\right)\right)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by Drexel28 View Post
    Indeed, obviously. But, you can do this for any set (intersection of sets, union of sets, etc.). Particularly, \left(A\cap B\right)\cup\left(A\cap C\right)=\left(A\cup\left(A\cap C\right)\right)\cap\left(B\cup\left(A\cap C\right)\right)
    Crap I meant \left(A\cap B\right)\cap\left(A\cap C\right). that would be \left(A\cap\left(A\cap C\right)\right)\cap\left(B\cap\left(A\cap C\right)\right)right?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bfpri View Post
    Crap I meant \left(A\cap B\right)\cap\left(A\cap C\right). that would be \left(A\cap\left(A\cap C\right)\right)\cap\left(B\cap\left(A\cap C\right)\right)right?
    Yezzir.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by Drexel28 View Post
    Yezzir.
    Wow, I just realized thats a heckuva lot of distributions I have to do to get \left|{A \cap B \cap C}\right| . Maybe i should just say.."Because of the distributive laws \left|{A \cap B \cup (A \cap C)}\right| = \left|{A \cap B \cap C}\right|.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bfpri View Post
    Wow, I just realized thats a heckuva lot of distributions I have to do to get \left|{A \cap B \cap C}\right| . Maybe i should just say.."Because of the distributive laws \left|{A \cap B \cup (A \cap C)}\right| = \left|{A \cap B \cap C}\right|.
    Haha! If it's right. To be one-hundred percent honest with you I haven't checked. In fact it isn't correct!

    A\cap \varnothing\cap C=\varnothing\ne \left(A\cap\varnothing\right)\cup\left(A\cap C\right)=A\cap C
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    whoops can you check \left(A\cap B\right)\cap\left(A\cap C\right)<br />
.. I copied it wrong..again
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bfpri View Post
    whoops can you check \left(A\cap B\right)\cap\left(A\cap C\right)<br />
.. I copied it wrong..again
    Oh, you! haha. Well in that case it's trivially true since the intersection operator is associative, commutative, and A\cap A=A
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Alright, Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 06:26 PM
  2. cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2010, 01:42 PM
  3. Cardinality of Sets
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 3rd 2010, 10:09 AM
  4. Prove that two sets have the same cardinality
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: March 17th 2010, 04:04 AM
  5. Cardinality of sets Q and R
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2009, 01:30 PM

Search Tags


/mathhelpforum @mathhelpforum