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,204 Thanks: 647  Quote:
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:
We never simply "run out of" natural numbers we can use as preimages where we can't simply remap f(x) to some other preimage. 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,204 Thanks: 647  I like your professor Quote:
Quote:
Quote:
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:
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,204 Thanks: 647  Quote:
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  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,204 Thanks: 647  Quote:
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:
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 preimage 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  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proof that Cantor's Theorem is Misunderstood  krausebj0  Number Theory  206  July 9th, 2013 07:10 PM 
power set of the natural numbers  blabla  Real Analysis  2  February 25th, 2012 01:31 PM 
Disproof of Cantor's theorem  krausebj0  Applied Math  6  November 29th, 2011 04:50 AM 
Cantor's Theorem  julian21  Number Theory  3  November 27th, 2010 10:47 PM 
CantorBendixson Theorem, uniqueness  pascal4542  Applied Math  0  April 17th, 2010 09:49 AM 