Results 1 to 7 of 7

Thread: 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
    $\displaystyle \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:
    $\displaystyle Let \; x\in A\cup B\cup \bar{C}$
    $\displaystyle \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
    21,797
    Thanks
    2828
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    Given that sets A, B, C are subsets of a finite set S prove that
    $\displaystyle \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.
    $\displaystyle |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:
    $\displaystyle |\overline{C}|=|S|-|C|$
    $\displaystyle |A\cap\overline{C}|=|A|-|A\cap C|$
    $\displaystyle |B\cap\overline{C}|=|B|-|B\cap C|$
    $\displaystyle |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 $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
    Because it feels like $\displaystyle A\cup B$ is already part of $\displaystyle \bar{C}$, ie: $\displaystyle (A\cup B) \subseteq \bar{C}$
    Then so $\displaystyle \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
    21,797
    Thanks
    2828
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    I suddenly got confused at one part.
    Is $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
    Because it feels like $\displaystyle A\cup B$ is already part of $\displaystyle \bar{C}$, ie: $\displaystyle (A\cup B) \subseteq \bar{C}$
    Then so $\displaystyle \left | A\cup B\cup \bar{C} \right |= \left | \bar{C} \right |$?
    $\displaystyle (A\cup B) \subseteq \overline{C}$, this true only if $\displaystyle (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
    $\displaystyle (A\cup B) \subseteq \overline{C}$, this true only if $\displaystyle (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 $\displaystyle \overline{C}$, isn't it?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,797
    Thanks
    2828
    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 $\displaystyle \overline{C}$, isn't it?
    $\displaystyle \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 $\displaystyle (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
    $\displaystyle \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 $\displaystyle (A\cup B)\subseteq \overline C~?$
    oh you are right! Maybe it is more appropriate to say $\displaystyle ((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: Sep 8th 2011, 05:26 PM
  2. Cardinality of these sets!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Aug 4th 2010, 07:27 AM
  3. Cardinality of Sets
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 3rd 2010, 09:09 AM
  4. Cardinality of sets Q and R
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 14th 2009, 12:30 PM
  5. Cardinality of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 18th 2007, 03:30 PM

Search Tags


/mathhelpforum @mathhelpforum