OK, I've never taken a class that covers set theory or anything, and my very limited knowledge of the subject is both recent and gleaned mostly from Wikipedia. I know that [imath]\mathcal{P}(\unicode{x2115})[/imath] is uncountable, although I haven't seen the proof. I want to try to figure it out on my own without seeing the proof, and I figure that shouldn't be all that hard since I already know it has something to do with Cantor's diagonal argument. The problem is that [imath]\mathcal{P}(\unicode{x2115})[/imath] seems countable to me, like so:

[math]\{

\emptyset,

\{\unicode{x2115}\},

\{1\},

\mathcal{P}\{1\},

\{1,2\},

\mathcal{P}\{1,2\},

\{1,2,3\},

\mathcal{P}\{1,2,3\},

\{1,2,3,4\},

\mathcal{P}\{1,2,3,4\},\dots

\}[/math]

I don't know if the notation is correct, but hopefully my meaning is clear. There will be a lot of repeats (for example, {1} is in every power set), but those can be skipped when counting.

What am I missing here? Either this set doesn't actually contain all of the subsets of [imath]\unicode{x2115}[/imath] (and obviously it seems to me like it does), or this set isn't countable (which, again, it seems to me like it is).

This is all new to me, so I'm probably overlooking something simple. Thanks!

## P(N) question

**Moderators:** gmalivuk, Moderators General, Prelates

### Re: P(N) question

First of all, your notation's a little bit strange, as your collection of sets includes both things like {1, 2, 3}, which is a set of numbers, and P({1, 2, 3}) with is a set of sets of numbers. If I were to guess, I'd say you were trying to list all the subsets of N by first listing all the subsets of the first 0 elements (i.e., the empty set), then all subsets of the first 1 elements (i.e., emptyset and {1}), then all subsets of the first 2 elements, and so on...

This is a useful construction, as far as it goes, and it definitely proves that the collection of all finite subsets of the natural numbers is countable. However, your list will never include any infinite subsets of N. For instance, the set of even numbers never shows up in your list. It is the existence of infinite subsets of N that makes P(N) uncountable.

This is a useful construction, as far as it goes, and it definitely proves that the collection of all finite subsets of the natural numbers is countable. However, your list will never include any infinite subsets of N. For instance, the set of even numbers never shows up in your list. It is the existence of infinite subsets of N that makes P(N) uncountable.

### Re: P(N) question

You are correct. That's what I was trying to do.

And now that you've explained it, it is indeed something simple that I was overlooking. P(N) contains an infinite number of infinite sets, so Cantor's diagonal argument applies just the same as it does to the set of irrational numbers, correct?

Now I need to figure out how to prove that the power set of any infinite set has higher cardinality than the set itself...

And now that you've explained it, it is indeed something simple that I was overlooking. P(N) contains an infinite number of infinite sets, so Cantor's diagonal argument applies just the same as it does to the set of irrational numbers, correct?

Now I need to figure out how to prove that the power set of any infinite set has higher cardinality than the set itself...

### Re: P(N) question

It helps in this case to show a more general fact that for every set X (not just infinite ones) there is no surjection from X to P(X). If you think about Cantor's argument in set-theoretic terms, you should be able to take any mapping from X to P(X) and construct a set S that is not in the range.

### Re: P(N) question

Spoilered for containing the answer.

**Spoiler:**

### Who is online

Users browsing this forum: No registered users and 6 guests