Results 1 to 7 of 7

Math Help - Proving cardinality of sets

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    Proving cardinality of sets

    Given that sets A, B, C are subsets of a finite set S prove that
    \left | A\cup B\cup \bar{C} \right | =\left | S \right | -\left | C \right |+\left | A\cap C \right | +\left | B\cap C \right | -\left | A\cap B\cap C \right |

    So I started of throwing a dummy element into the sets that I will keep track of:
    Let \; x\in A\cup B\cup \bar{C}
    \Rightarrow x\in A \; or \; x\in B \; or \; x\notin C

    Then I list out all the possible cases:


    Since in all the cases, the cardinality are equal to 1, can I say that hence the theorem is proven?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    Given that sets A, B, C are subsets of a finite set S prove that
    \left | A\cup B\cup \bar{C} \right | =\left | S \right | -\left | C \right |+\left | A\cap C \right | +\left | B\cap C \right | -\left | A\cap B\cap C \right |
    I would start out with this.
    |A\cup B\cup\overline{C}|=|A|+|B|+|\overline{C}|-|A\cap B|-|A\cap\overline{C}|-|B\cap\overline{C}|+|A\cap B\cap\overline{C}|
    Then note four facts:
    |\overline{C}|=|S|-|C|
    |A\cap\overline{C}|=|A|-|A\cap C|
    |B\cap\overline{C}|=|B|-|B\cap C|
    |A\cap B\cap\overline{C}|=|A\cap B|-|A\cap B\cap C|
    Substitute.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    95
    I suddenly got confused at one part.
    Is \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |?
    Because it feels like A\cup B is already part of \bar{C}, ie: (A\cup B) \subseteq  \bar{C}
    Then so \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    I suddenly got confused at one part.
    Is \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |?
    Because it feels like A\cup B is already part of \bar{C}, ie: (A\cup B) \subseteq  \bar{C}
    Then so \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |?
    (A\cup B) \subseteq  \overline{C}, this true only if (A\cup B)\cap C=\emptyset .
    Otherwise, it is not true.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    Posts
    95
    Quote Originally Posted by Plato View Post
    (A\cup B) \subseteq  \overline{C}, this true only if (A\cup B)\cap C=\emptyset .
    Otherwise, it is not true.
    Why is it true only if it is an empty set?
    Any elements in A or in B or in both or somewhere in the universal set outside of C, as long as it is not in C, it is considered \overline{C}, isn't it?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,922
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    Why is it true only if it is an empty set?
    Any elements in A or in B or in both or somewhere in the universal set outside of C, as long as it is not in C, it is considered \overline{C}, isn't it?
    \begin{gathered}  S = \left\{ {0,1,2,3,4,5,6,7,8,9} \right\} \hfill \\  A = \left\{ {0,1,2,3,4} \right\} \hfill \\  B = \left\{ {1,3,5,7,9} \right\} \hfill \\  C = \left\{ {4,5,6,7} \right\}\;\& \;\overline C  = \left\{ {0,1,2,3,8,9} \right\} \hfill \\ \end{gathered}
    Now is (A\cup B)\subseteq \overline C~?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    Posts
    95
    Quote Originally Posted by Plato View Post
    \begin{gathered}  S = \left\{ {0,1,2,3,4,5,6,7,8,9} \right\} \hfill \\  A = \left\{ {0,1,2,3,4} \right\} \hfill \\  B = \left\{ {1,3,5,7,9} \right\} \hfill \\  C = \left\{ {4,5,6,7} \right\}\;\& \;\overline C  = \left\{ {0,1,2,3,8,9} \right\} \hfill \\ \end{gathered}
    Now is (A\cup B)\subseteq \overline C~?
    oh you are right! Maybe it is more appropriate to say ((A \cup B)\cap \overline{C})\subseteq \overline{C}. 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 these sets!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 4th 2010, 08:27 AM
  3. Cardinality of Sets
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 3rd 2010, 10:09 AM
  4. Cardinality of sets Q and R
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2009, 01:30 PM
  5. Cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2007, 04:30 PM

Search Tags


/mathhelpforum @mathhelpforum