## P(N) question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

hencethus
Posts: 24
Joined: Thu May 31, 2007 4:25 am UTC
Location: Port Orange, FL
Contact:

### P(N) question

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:
$\{ \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 \}$

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!

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

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

hencethus
Posts: 24
Joined: Thu May 31, 2007 4:25 am UTC
Location: Port Orange, FL
Contact:

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

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

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

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

### Re: P(N) question

Spoiler:
So, this proof was first explained to me thusly: The short answer is 'consider the set of all spies who don't spy on themselves'. My first-year professor at college was Russian, and apparently starting a mathematical analogy with 'so, the entire population is composed of spies' is normal there...

Anyways, you have a population of spies. This being a very paranoid society, we want to make sure that each group of spies is itself being spied on. So we assign each spy a subset of the spies to spy on. He may himself either be in this group or not. We'd like it to be the case that every subset of spies is being spied on (i.e., we have a surjection from spies to sets of spies). However, consider the set of all spies who do not spy on themselves (i.e., the spies s who are not in the group f(s) assigned to them). This set S can't be spied upon, because if it is, there is some spy s spying on it. Then, is s in S? If he is, then he's in the group assigned to him, breaking the rule for S. If he's not, then he's not in the group he's spying on, so he should be in S, again breaking the rule for S. Either way, such an s cannot exist, so we miss at least one group.

This is of course the standard proof. But years later, I still can't decide if the analogy is more or less confusing than the straight-up proof... Maybe I'm just distracted by all the spies.