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(\oslash)
b. P(P(\oslash))
c. P(P(P(\oslash)))

Homework Equations

n/a

The Attempt at a Solution

a. since the set in question is the null set, the answer is {\oslash} - cardinality 1
b. since the set in question is the set that contains the null set, the answer is {\oslash,{\oslash}} - cardinality 2
c. Now this is one that I'm starting to have trouble with. I can simplify the problem to P({\oslash,{\oslash}}). My answer is: {\oslash,{\oslash},{\oslash,{\oslash}}} - 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(\oslash)
b. P(P(\oslash))
c. P(P(P(\oslash)))

Homework Equations

n/a

The Attempt at a Solution

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

Correct!

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

If I have difficulty in seeing things, I introduce some variables. Let's do that here. Put A=\emptyset,~~B=\{\emptyset\}[/tex].<br /> Then the question asks you to find P({A,B}), can you do that?<br /> <br /> Hint: to see immediately if an answer is right or wrong: the cardinality of a power set is <b>always</b> 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 A=\emptyset,~~B=\{\emptyset\}[/tex].<br /> Then the question asks you to find P({A,B}), can you do that?

<br /> <br /> 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?<br /> <br /> \oslash , {\oslash}, {{\oslash}}, {\oslash,{\oslash}}<br /> <br /> Is that answer correct now?<br /> <br /> <blockquote data-attributes="" data-quote="micromass" data-source="post: 3348534" class="bbCodeBlock bbCodeBlock--expandable bbCodeBlock--quote js-expandWatch"> <div class="bbCodeBlock-title"> micromass said: </div> <div class="bbCodeBlock-content"> <div class="bbCodeBlock-expandContent js-expandContent "> Hint: to see immediately if an answer is right or wrong: the cardinality of a power set is <b>always</b> a power of 2. In particular, if X has n elements, then |P(X)|=2ⁿ. </div> </div> </blockquote><br /> That&#039;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?

\oslash , {\oslash}, {{\oslash}}, {\oslash,{\oslash}}

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ⁿ.