
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?

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^{n1}$ subsets of $\displaystyle A$ that contain the number $\displaystyle 1$.
So there are $\displaystyle 2^{n1}$ pairs in $\displaystyle D$ having $\displaystyle 1$ as the first term.
Therefore, how many pairs are there in $\displaystyle D~?$

Why $\displaystyle 2^{n1}$? Surely it would be $\displaystyle 2^n$?

No wait I see it now. So the answer should be $\displaystyle n{2^{n1}}$?


Awesome, thanks for the help!