I'm stuck on this question:

Let A={1,2,3....,n}. What is the cardinality of the set:

{(a,S) : a S, S 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?

Printable View

- Dec 7th 2010, 10:00 AMworc3247Cardinality
I'm stuck on this question:

Let A={1,2,3....,n}. What is the cardinality of the set:

{(a,S) : a S, S 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, 10:47 AMPlato
Let , then we are counting the number of ordered pairs in .

There are subsets of that contain the number .

So there are pairs in having as the first term.

Therefore, how many pairs are there in - Dec 7th 2010, 10:51 AMworc3247
Why ? Surely it would be ?

- Dec 7th 2010, 10:53 AMworc3247
No wait I see it now. So the answer should be ?

- Dec 7th 2010, 10:57 AMPlato
You have it.

- Dec 7th 2010, 11:01 AMworc3247
Awesome, thanks for the help!