Results 1 to 4 of 4

Thread: Cardinality of a set

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Cardinality of a set

    How can I show that the set {$\displaystyle (A, B) \in P(S) \times P(S) | A \subseteq B$} contains $\displaystyle 3^n$ elements, where S is a set of n elements and P(S) is the power set of S.

    [SOLVED]
    Last edited by posix_memalign; Apr 30th 2010 at 01:54 AM. Reason: Solved
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    Let S be a set of n elements and consider the power set P(S) of S.
    How can I show that the set {$\displaystyle (A, B) \in P(S) \times P(S) | A \subseteq B$} contains $\displaystyle 3^n$ elements?
    Here is some notation. $\displaystyle |A|$ is the number of elements is set $\displaystyle A$.
    Thus $\displaystyle |S|=n$ and $\displaystyle |\mathcal{P}(S)|=2^n$.

    For each set $\displaystyle A$ that are $\displaystyle 2^{n-|A|}$ subsets of $\displaystyle S$ that are super-sets of $\displaystyle A$
    i.e. $\displaystyle |\{X\in \mathcal{P}(S):A\subseteq X\}|=2^{n-|A|}$
    Hence that is the number of wanted pairs $\displaystyle (A,B)$.

    To count them find the sum $\displaystyle \sum\limits_{k = 0}^n {\binom{n}{k} \cdot 2^{n - k} } $. Do you see why?

    Now use the binomial expansion theorem on $\displaystyle 3^n=(1+2)^n$
    Last edited by Plato; Apr 29th 2010 at 03:15 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Plato View Post
    To count them find the sum $\displaystyle \sum\limits_{k = 0}^n {\binom{n}{k} \cdot 2^{n - k} } $. Do you see why?
    After you have arrived at this then it is obvious why it is $\displaystyle 3^n$ but I don't see how you arrive at this statement unfortunately no.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    After you have arrived at this then it is obvious why it is $\displaystyle 3^n$ but I don't see how you arrive at this statement unfortunately no.
    Then I must ask you if you understand that the number of subsets having
    $\displaystyle A$ as a subset is $\displaystyle 2^{n-|A|}?$
    If you do then there are $\displaystyle \sum\limits_{k = 0}^n {\binom{n}{k}} $ subsets of each ‘size’.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: Mar 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Feb 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Feb 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum