It is a fact that if $A$ is any set then there is no bijection between $A$ and its powerset $P(A)$. If $A$ is finite, this is pretty clear just by looking at the sizes of $A$ and $P(A)$. But if I don't know this and I try finding a bijection between $\mathbb{N}$ and $P(\mathbb{N})$, what would stop me from trying to build a function that recursively enumerates the contents of $P(\mathbb{N})$?

  • 2
    $\begingroup$ You mean, aside from the proof that you can't? You started this question by saying "It is a fact..." that you can't. $\endgroup$ – Thomas Andrews Jan 25 '15 at 0:28
  • $\begingroup$ Nothing stops you from trying - it success that Cantor's theorem prohibits. (And that theorem doesn't even need the axiom of choice or anything like that - it's pretty primitive) $\endgroup$ – Milo Brandt Jan 25 '15 at 0:30
  • $\begingroup$ @ThomasAndrews Yes, if I didn't know a priori that P(A) isn't denumerable, what would be wrong conceptually with any such function that I 'claim' does the job? Maybe this is just circular and I'm being stupid, I don't know. $\endgroup$ – user210359 Jan 25 '15 at 0:31
  • $\begingroup$ Have you seen the proof? The proof finds, for any $f:A\to P(A)$ an element of $P(A)$ not in the range of $f$. $\endgroup$ – Thomas Andrews Jan 25 '15 at 0:32
  • $\begingroup$ you won't find any such function because no such function exists because of Cantor's theorem, hence you can't find such a function, as no such functions exists, due to Cantor's theorem... $\endgroup$ – Ittay Weiss Jan 25 '15 at 0:32

It seems you are somehow saying that, using recursion, you can define some function which avoids the error.

But the proof that no $f:A\to P(A)$ uses the whole function $f$. If you give me a complete definition of a function $f:A\to P(A)$, I can find an element of $P(A)$ which is not in the image of $f$. Recursion doesn't let you get around this. You can change the function, but that new function also misses some set.

This would be like saying Euclid's proof doesn't prove that the primes are infinite, because, once you find that extra prime, you can just add it to the set, and you still have a finite set of primes.

  • 1
    $\begingroup$ This reminds me a bit of the time when someone proposed to prove by induction that $\pi$ is rational. The argument said that every time you add another digit to a truncation of the decimal expansion of $\pi$, what you get is still rational. I answered that the same argument proves that $\mathbb N$ is finite (every time you add an element to a finite set, what you get is still finite). $\endgroup$ – Michael Hardy Jan 25 '15 at 0:47
  • $\begingroup$ @MichaelHardy Okay, thank you very much to Thomas for the nice answer. However, to be clear, I wasn't proposing the hypothetical method I'm asking about as a correct method. What I was asking about was what is the precise reason that it doesn't work. I could do without the condescension, I have already acknowledged that my question was probably a bad one! $\endgroup$ – user210359 Jan 25 '15 at 0:52
  • $\begingroup$ You keep taking offense. Really, a lot of people have trouble with these concepts, and I've found that a lot of different approaches clarify things, depending on the person. Since we don't know you, we took several different tacks to try to jostle you from your confusion. @user210359 $\endgroup$ – Thomas Andrews Jan 25 '15 at 0:54
  • $\begingroup$ The precise reason why it doesn't work is precisely the proof of Cantor's theorem. I've posted that proof as an answer here. $\endgroup$ – Michael Hardy Jan 25 '15 at 0:59
  • $\begingroup$ @user210359 And yes, I understand what you were driving at now, but you included the specific idea of defining the function recursively, which led me astray from the real question you were asking. Why did you include the 'recursive' condition? $\endgroup$ – Thomas Andrews Jan 25 '15 at 1:07

If you have a function $f:\mathbb N\to\mathcal P(\mathbb N)$, then let $$ B = \{ n\in\mathbb N : n\not\in f(n) \}. $$ Then $B$ is not in the image of $f$. To prove this, suppose $B = f(k)$. Then ask whether $k\in B$ or not. If it is, then it's not, and if it's not, then it is. Either way, you have a contradiction. Hence every such function $f$ fails to be onto the entire set $\mathcal P(\mathbb N)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.