Results 1 to 4 of 4

Math Help - Cardinality of a set

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Cardinality of a set

    How can I show that the set { (A, B) \in P(S) \times P(S) | A \subseteq B} contains 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; April 30th 2010 at 01:54 AM. Reason: Solved
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    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 { (A, B) \in P(S) \times P(S) | A \subseteq B} contains 3^n elements?
    Here is some notation. |A| is the number of elements is set A.
    Thus |S|=n and |\mathcal{P}(S)|=2^n.

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

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

    Now use the binomial expansion theorem on 3^n=(1+2)^n
    Last edited by Plato; April 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 \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 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
    18,803
    Thanks
    1692
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    After you have arrived at this then it is obvious why it is 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
    A as a subset is 2^{n-|A|}?
    If you do then there are \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: March 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum