Cardinality

**worc3247** · December 7th 2010, 09:00 AM

I'm stuck on this question:
Let A={1,2,3....,n}. What is the cardinality of the set:
{(a,S) : a $\in$ S, S $\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?

**Plato** · December 7th 2010, 09:47 AM

Let $D = \left\{ {(a,S):a \in S \in \mathcal{P}(A)} \right\}$ , then we are counting the number of ordered pairs in $D$ .
There are $2^{n-1}$ subsets of $A$ that contain the number $1$ .
So there are $2^{n-1}$ pairs in $D$ having $1$ as the first term.
Therefore, how many pairs are there in $D~?$

**worc3247** · December 7th 2010, 09:51 AM

Why $2^{n-1}$ ? Surely it would be $2^n$ ?

**worc3247** · December 7th 2010, 09:53 AM

No wait I see it now. So the answer should be $n{2^{n-1}}$ ?

**Plato** · December 7th 2010, 09:57 AM

You have it.

**worc3247** · December 7th 2010, 10:01 AM

Awesome, thanks for the help!

Thread: Cardinality

LinkBack

Thread Tools

Display

Cardinality

Similar Math Help Forum Discussions

Cardinality

Cardinality of R, [0,1], R^2, [0,1] x [0,1]

Cardinality

Cardinality

Cardinality

Search Tags