Results 1 to 6 of 6

Thread: Cardinality

  1. #1
    Member
    Joined
    Dec 2010
    Posts
    107

    Cardinality

    I'm stuck on this question:
    Let A={1,2,3....,n}. What is the cardinality of the set:
    {(a,S) : a$\displaystyle \in$S, S$\displaystyle \in$P(A)}.

    I feel like its going to be related to 2^n, but i'm not sure. Could someone point me in the right direction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,797
    Thanks
    2828
    Awards
    1
    Let $\displaystyle D = \left\{ {(a,S):a \in S \in \mathcal{P}(A)} \right\}$, then we are counting the number of ordered pairs in $\displaystyle D$.
    There are $\displaystyle 2^{n-1}$ subsets of $\displaystyle A$ that contain the number $\displaystyle 1$.
    So there are $\displaystyle 2^{n-1}$ pairs in $\displaystyle D$ having $\displaystyle 1$ as the first term.
    Therefore, how many pairs are there in $\displaystyle D~?$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2010
    Posts
    107
    Why $\displaystyle 2^{n-1}$? Surely it would be $\displaystyle 2^n$?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2010
    Posts
    107
    No wait I see it now. So the answer should be $\displaystyle n{2^{n-1}}$?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,797
    Thanks
    2828
    Awards
    1
    You have it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2010
    Posts
    107
    Awesome, thanks for the help!
    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