What Is the Cardinality of Nested Power Sets?

[battousai]

Homework Statement

I'm having a little bit of trouble grasping the idea of null sets and power sets. Please check my answers to the following questions:

Determine the cardinality:

a. P([itex]\oslash[/itex])
b. P(P([itex]\oslash[/itex]))
c. P(P(P([itex]\oslash[/itex])))

Homework Equations

n/a

The Attempt at a Solution

a. since the set in question is the null set, the answer is {[itex]\oslash[/itex]} - cardinality 1
b. since the set in question is the set that contains the null set, the answer is {[itex]\oslash[/itex],{[itex]\oslash[/itex]}} - cardinality 2
c. Now this is one that I'm starting to have trouble with. I can simplify the problem to P({[itex]\oslash[/itex],{[itex]\oslash[/itex]}}). My answer is: {[itex]\oslash[/itex],{[itex]\oslash[/itex]},{[itex]\oslash[/itex],{[itex]\oslash[/itex]}}} - cardinality 3.

Is that right, or am I missing something?

 

[micromass]

Hi battousai!

Homework Statement

I'm having a little bit of trouble grasping the idea of null sets and power sets. Please check my answers to the following questions:

Determine the cardinality:

a. P([itex]\oslash[/itex])
b. P(P([itex]\oslash[/itex]))
c. P(P(P([itex]\oslash[/itex])))

Homework Equations

n/a

The Attempt at a Solution

a. since the set in question is the null set, the answer is {[itex]\oslash[/itex]} - cardinality 1
b. since the set in question is the set that contains the null set, the answer is {[itex]\oslash[/itex],{[itex]\oslash[/itex]}} - cardinality 2

Correct!

c. Now this is one that I'm starting to have trouble with. I can simplify the problem to P({[itex]\oslash[/itex],{[itex]\oslash[/itex]}}). My answer is: {[itex]\oslash[/itex],{[itex]\oslash[/itex]},{[itex]\oslash[/itex],{[itex]\oslash[/itex]}}} - cardinality 3.

If I have difficulty in seeing things, I introduce some variables. Let's do that here. Put [itex]A=\emptyset,~~B=\{\emptyset\}[/tex].
Then the question asks you to find P({A,B}), can you do that?

Hint: to see immediately if an answer is right or wrong: the cardinality of a power set is always a power of 2. In particular, if X has n elements, then |P(X)|=2ⁿ.

 

[battousai]

Hi battousai!
Correct!
If I have difficulty in seeing things, I introduce some variables. Let's do that here. Put [itex]A=\emptyset,~~B=\{\emptyset\}[/tex].
Then the question asks you to find P({A,B}), can you do that?

Hm, I get cardinality 4 when I do it with A and B. Now when we go back to the original elements, what would be the elements of the power set?

[itex]\oslash[/itex] , {[itex]\oslash[/itex]}, {{[itex]\oslash[/itex]}}, {[itex]\oslash[/itex],{[itex]\oslash[/itex]}}

Is that answer correct now?

Hint: to see immediately if an answer is right or wrong: the cardinality of a power set is always a power of 2. In particular, if X has n elements, then |P(X)|=2ⁿ.

That's neat! How does one prove that?

 

[micromass]

Hm, I get cardinality 4 when I do it with A and B. Now when we go back to the original elements, what would be the elements of the power set?

[itex]\oslash[/itex] , {[itex]\oslash[/itex]}, {{[itex]\oslash[/itex]}}, {[itex]\oslash[/itex],{[itex]\oslash[/itex]}}

Is that answer correct now?

That's good!

That's neat! How does one prove that?

Hmm, I hope you know something of combinatorics. You can form an arbitrary subset of X by choosing for each element of X whether that element belongs to X or not. For example, the subset {0} of {0,1} is formed by deciding that 0 is in the subset and that 1 is not.
So, for each element, we have 2 choices: in the subset or not. So in total, we have 2*2*2*...*2=2ⁿ possibilities! So that's the size of the power set!

 

[battousai]

I don't know much about combinatorics, but that explanation makes sense. Thanks!

 

[HallsofIvy]

You can also prove that if |A|= n, then |P(A)|= 2ⁿ by induction on n. If A is empty, |A|= 0, then P(A) contains only the empty set, as you showed, so |P(A)|= 1= 2⁰.

If A is not empty, let x be a specific member of A. There exist two kinds of subsets of A- those that contain x and those that do not. A, with x removed, has n-1 members so there are 2^n-1 subsets of A that do not contain x. But every subset of A that does contain x is just a subset of A that does not contain x union {x}. That is, there are also 2^n-1 subsets of A that do contain x. The total of all subsets of A is 2^n-1+ 2^n-1= 2(2^n-1)= 2ⁿ.