 My Math Forum Question on the countability of the power set of natural numbers (Cantor's theorem)

 Number Theory Number Theory Math Forum

 February 24th, 2016, 01:15 PM #1 Newbie   Joined: Mar 2013 Posts: 24 Thanks: 0 Question on the countability of the power set of natural numbers (Cantor's theorem) I've been trying, on and off, for weeks now, to wrap my head around this theorem, but I keep running into issues with it. I think I finally have some definitive question(s) to ask, though. Questions I haven't found any documentation of anyone asking. So we are meant to assume that $\mathcal{P}(\mathbb{N})$ is countable, and that $\mathcal{f}: \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})$ in order to arrive at a contradiction. So we construct the set $\mathcal{X} = \{ x | x \in \mathbb{N} \space and \space x \notin \mathcal{f}(x) \}$ and establish that $\mathcal{X} \in \mathcal{P}(\mathbb{N})$. Okay, so far so good. Here is where I'm having a disconnect of following the logic. The proof claims that since $\mathcal{f}$ is a bijection, we must have $\mathcal{X} = \mathcal{f}(x)$ for some $x$. Why? The punch line: $x \in \mathcal{X} \iff x \notin \mathcal{f}(x) = \mathcal{X}$ Lets say $\mathcal{Q}$ is the set of all such $\mathcal{X}$ as defined above. Now lets define $\mathcal{R}$ as the set of all sets $\mathcal{Y} = \{ y | y \in \mathbb{N} \space and \space y \in \mathcal{f}(y) \}$ Then $\mathcal{Q} \subset \mathcal{P}(\mathbb{N}) \space and \space \mathcal{R} \subset \mathcal{P}(\mathbb{N})$. What I see, is the implication that $\mathcal{Q} \cap \mathcal{R} \neq \emptyset$, but clearly, these two sets need not intersect. What am I missing in the properties of a bijection that means there must be $\mathcal{X} = \mathcal{f}(x)$ for some $x$? The definition of $\mathcal{X}$ says it all, and from my definitions, $\mathcal{Q}$ does not contain any such members where $\mathcal{X} = \mathcal{f}(x) \space and \space x \in \mathcal{X}$. Since $\mathbb{N}$ is an infinite set, and so is $\mathcal{P}(\mathbb{N})$ I don't see where the intersection $\mathcal{Q} \cap \mathcal{R}$ must occur. Is this a condition of reflection? February 24th, 2016, 01:40 PM   #2
Senior Member

Joined: Aug 2012

Posts: 2,323
Thanks: 715

Quote:
 Originally Posted by Polaris84 Here is where I'm having a disconnect of following the logic. The proof claims that since $\mathcal{f}$ is a bijection, we must have $\mathcal{X} = \mathcal{f}(x)$ for some $x$. Why?
Because a bijection is, in particular, a surjection. That means that everything in the target space gets hit. $\mathcal{X}$ is an element of $\mathcal{P}(\mathbb{N})$ so there must be some element that hits it.

By the way this proof is far more general. It applies to any set, not just a countable one. So that aspect is best omitted, you don't need that assumption. This proof shows that there is never a bijection between a set and its powerset.

Last edited by Maschke; February 24th, 2016 at 01:43 PM. February 24th, 2016, 02:10 PM   #3
Newbie

Joined: Mar 2013

Posts: 24
Thanks: 0

Quote:
 Originally Posted by Maschke Because a bijection is, in particular, a surjection. That means that everything in the target space gets hit. $\mathcal{X}$ is an element of $\mathcal{P}(\mathbb{N})$ so there must be some element that hits it. By the way this proof is far more general. It applies to any set, not just a countable one. So that aspect is best omitted, you don't need that assumption. This proof shows that there is never a bijection between a set and its powerset.
My professor mentioned that it applies to any set. Still though, a surjection simply states every possible image has an associated pre-image. And since we assumed it was a bijection, this means that each pre-image must also be unique for every image. So where is the requirement that eventually there must be an $x \in \mathcal{X} \space and \space x \in \mathcal{f}(x)$? For every $\mathcal{X} \in \mathcal{P}(\mathbb{N})$, we can effectively avoid the situation where this contradiction would occur forever, because both $\mathcal{P}(\mathbb{N})$ and $\mathbb{N}$ are infinite sets.

We never simply "run out of" natural numbers we can use as pre-images where we can't simply remap f(x) to some other pre-image.

Last edited by Polaris84; February 24th, 2016 at 02:16 PM. February 24th, 2016, 03:30 PM #4 Newbie   Joined: Mar 2013 Posts: 24 Thanks: 0 I guess what I'm trying to say is that for every possible $\mathcal{X} \in \mathcal{P}(\mathbb{N})$, there is some $z \in \mathbb{N}$ where $z \neq x$ and $z \notin \mathcal{X}$ and $\mathcal{f}(z) = \mathcal{X}$. For the contradiction to exist, then my above statement can't be true. February 24th, 2016, 04:45 PM   #5
Senior Member

Joined: Aug 2012

Posts: 2,323
Thanks: 715

Quote:
 Originally Posted by Polaris84 My professor mentioned that it applies to any set.
I like your professor Quote:
 Originally Posted by Polaris84 Still though, a surjection simply states every possible image has an associated pre-image.
Yes.

Quote:
 Originally Posted by Polaris84 And since we assumed it was a bijection, this means that each pre-image must also be unique for every image.
Yes.

Quote:
 Originally Posted by Polaris84 So where is the requirement that eventually there must be an $x \in \mathcal{X} \space and \space x \in \mathcal{f}(x)$? For every $\mathcal{X} \in \mathcal{P}(\mathbb{N})$, we can effectively avoid the situation where this contradiction would occur forever, because both $\mathcal{P}(\mathbb{N})$ and $\mathbb{N}$ are infinite sets. We never simply "run out of" natural numbers we can use as pre-images where we can't simply remap f(x) to some other pre-image.
No. You are not required to find or construct the preimage in any way. f is a surjection. Therefore everything gets hit, period. I do not need to name, identify, construct, or characterize this unique element of the preimage in any way, shape, or form. It's sufficient to know that it exists.

This is what in math is called a statement of existence. In math when we say something exists, it exists. We don't need to know any more about it.

I can see that this is probably a stumbling block for modern students who are exposed to computer programming long before they ever see formal math. And in general, learning to reason about infinite sets is always a hurdle to be crossed.

If f is a surjection and y is some element in the target, then there exists some x in the domain such that f(x) = y. And that's all we care about: that x must exist.

Last edited by Maschke; February 24th, 2016 at 04:49 PM. February 24th, 2016, 06:23 PM   #6
Newbie

Joined: Mar 2013

Posts: 24
Thanks: 0

Quote:
 Originally Posted by Maschke If f is a surjection and y is some element in the target, then there exists some x in the domain such that f(x) = y. And that's all we care about: that x must exist.
Thank you for trying to explain. I'm really not trying to be difficult. I really just want to understand.

If the proof said that all members of P(N) are sets defined as X, then I could understand where you would run into a contradiction.

But strictly speaking, X is the set of all elements in N which, when mapped, do not produce a set that contains itself as a member. X is a single member P(N).

Saying that there must exist an $x \in \mathcal{X}$ such that $x \in \mathcal{f}(x) = \mathcal{X}$ literally just ignores the definition of what we set $\mathcal{X}$ to be. Its forcing a contradiction to exist where there isn't naturally a contradiction, at least from every angle I've looked at it (and I know I'm wrong, but I can't see how). If $x \in \mathcal{f}(x)$ were true, it would never qualify to be in $\mathcal{X}$, by its own definition.

EDIT: x is in the domain, but if f(x) -> X, then X $\neq$ f(x) by the very definition of X.

Last edited by Polaris84; February 24th, 2016 at 06:26 PM. February 24th, 2016, 06:27 PM   #7
Senior Member

Joined: Aug 2012

Posts: 2,323
Thanks: 715

Quote:
 Originally Posted by Polaris84 If $x \in \mathcal{f}(x)$ were true, it would never qualify to be in $\mathcal{X}$, by its own definition.
Yes exactly! If it is it isn't. And, if it isn't it is. Contradiction! Therefore there is no bijection.

I didn't address the rest of your post yet but this point is the heart of the matter. If we assume f is a bijection we derive a contradiction. $\displaystyle x \in \mathcal{X}$ if and only if $\displaystyle x \notin \mathcal{X}$. Therefore f is not a bijection. And since f was any bijection, that shows there isn't one.

Last edited by Maschke; February 24th, 2016 at 06:31 PM. February 24th, 2016, 06:39 PM   #8
Newbie

Joined: Mar 2013

Posts: 24
Thanks: 0

Quote:
 Originally Posted by Maschke Therefore f is not a bijection. And since f was any bijection, that shows there isn't one.
Okay, if I understand this correctly, if I can show that there is some bijection, or arrangement of the mapping between N and P(N) that doesn't hold, then that is all that matters? February 24th, 2016, 06:56 PM   #9
Senior Member

Joined: Aug 2012

Posts: 2,323
Thanks: 715

Quote:
 Originally Posted by Polaris84 Okay, if I understand this correctly, if I can show that there is some bijection, or arrangement of the mapping between N and P(N) that doesn't hold, then that is all that matters?
I'm not sure I understand what you wrote.

f is an arbitrary function from N to P(N). The assumption that f is a bijection leads to a contradiction. Therefore f is not a bijection.

ps -- Have you walked through the details of the argument for a small set, say one with 3 elements and 8 subsets? It might be helpful.

Last edited by Maschke; February 24th, 2016 at 07:21 PM. February 24th, 2016, 07:40 PM   #10
Newbie

Joined: Mar 2013

Posts: 24
Thanks: 0

Quote:
 Originally Posted by Maschke I'm not sure I understand what you wrote. f is an arbitrary function from N to P(N). The assumption that f is a bijection leads to a contradiction. Therefore f is not a bijection. ps -- Have you walked through the details of the argument for a small set, say one with 3 elements and 6 subsets? It might be helpful.
But I thought that all finite sets are countable? with 3 elements and 6 subsets, the pigeon hole principal applies, and the elements must repeat.

I may just be reaching the limits of my understanding for now. I can't explain myself any clearer, so I guess I'll either have to wait until I have better tools to form questions, or just give up, because in the end, I'm not a math major, or even a minor, lol, I just like being able to understand.

I just can't understand how there obviously is a set X in P(N), that is a fact, that has to exist. But then we say that there has to be an x that is both a member of X and f(x). X is defined so that this doesn't happen, and we can still map some n in N to f(n) = X, where n $\neq$ x. In those cases, n can be in f(n), because n isn't in X. And all x's map to a single set that is a member of P(N) that does not contain the same x. You will never run out of numbers that aren't in X that can map to sets containing themselves. Just the same, you will never run out of numbers that are in X which don't map to sets that contain themselves.

I just can't explain my misunderstanding any better. $x \in \mathcal{X}$ so that means there is some $n$ where $\mathcal{f}(n) = \mathcal{X}$ and $n \notin X$. This means that there is no $x = n$. The statement that $x \in X \iff x \notin \mathcal{f}(x) = \mathcal{X}$ appears contrived from no where. There is no obvious $\mathcal{X}$ where $x \in \mathcal{f}(x)$ must be true. In the bijection, $\mathcal{X}$ only requires 1 pre-image to map to it that isn't a member of $\mathcal{X}$, which can easily be produced.

***EDIT*** Perhaps this is what I have been miss interpreting:

$\mathcal{X}$ must contain every member of $\mathbb{N}$ but some how simultaneously excludes $x \notin \mathcal{f}(x)$? Because I've been reading it as $\mathcal{X}$ must contain every member of $\mathbb{N}$ except $x \notin \mathcal{f}(x)$...

Last edited by Polaris84; February 24th, 2016 at 08:32 PM. Tags cantor, countability, natural, numbers, power, question, set, theorem Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post krausebj0 Number Theory 206 July 9th, 2013 07:10 PM blabla Real Analysis 2 February 25th, 2012 01:31 PM krausebj0 Applied Math 6 November 29th, 2011 04:50 AM julian21 Number Theory 3 November 27th, 2010 10:47 PM pascal4542 Applied Math 0 April 17th, 2010 09:49 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      