# Cardinality

• Dec 7th 2010, 09:00 AM
worc3247
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?
• Dec 7th 2010, 09:47 AM
Plato
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~?$
• Dec 7th 2010, 09:51 AM
worc3247
Why $\displaystyle 2^{n-1}$? Surely it would be $\displaystyle 2^n$?
• Dec 7th 2010, 09:53 AM
worc3247
No wait I see it now. So the answer should be $\displaystyle n{2^{n-1}}$?
• Dec 7th 2010, 09:57 AM
Plato
You have it.
• Dec 7th 2010, 10:01 AM
worc3247
Awesome, thanks for the help!