1
$\begingroup$

I came up with a proof that the power set of natural numbers is countable, which obviously must be a wrong proof.

Here is a procedure to create a one-on-one correspondence between the natural numbers and the elements of its power set.

Starting with the power-set-element-counter k = 1. Go through all the natural numbers x in order (x = 1, x=2, etc), and for each x do the following:

  • Denote P(x) to be the set of all subsets of the set of natural numbers up to x: P(x) = Power{1,...,x}.
  • Denote P*(x) to be the the set of elements of P(x), excluding the elements in P(x-1).
  • P*(x) is finite, since the cardinality of a power set of a finite set is also finite. Denote the cardinality of P*(x) as "c". Hence we can pair the natural numbers, starting with k, to each of the elements in P*(x). After each pair that is paired, increment k = k+1. in the end, k will be incremented by c.
  • set x = x+1, and start the cycle over again.

This cycle should produce a bijection between the natural numbers and the elements of the power set of natural numbers. What is wrong with this proof?

$\endgroup$
7
$\begingroup$

Every single subset your procedure produces is finite. You've missed ALL of the infinite subsets. It turns out there's a whopping great lot of infinite subsets.

$\endgroup$
4
  • $\begingroup$ Ah i see. I did not think about the infinite subsets. This makes me wonder: Does it ever happen that a mathematician publishes a paper, and turns out to have completely neglected, or not considered, a crucial element or possibility, causing the proof to be invalid? Is this something that only happens to beginners like myself? Do professional mathematicians have a way to systematically prevent mistakes like this? $\endgroup$ – user56834 Sep 13 '16 at 14:51
  • 1
    $\begingroup$ Reputable journals have all papers peer-reviewed, which cuts way down on mistakes. Occasionally a mistake is caught and then a retraction or correction is printed. No doubt there are mistakes that aren't caught, but if the result is really important (so that many others are reading and using it) the mistake will eventually come out. $\endgroup$ – B. Goddard Sep 13 '16 at 14:54
  • $\begingroup$ So there isn't any kind of "systematic, fool-proof" way of making absolutely sure there are no mistakes caused by accidentally ignoring something? We just have to rely on the focus of mathematicians, which will make sure that the odds of such a mistake are very small? $\endgroup$ – user56834 Sep 13 '16 at 15:12
  • $\begingroup$ If the mistake is in something that "matters", then the odds will decrease to zero with time. A parallel is the math topics on Wikipedia. Wiki has a reputation of being "not that accurate" in general, but the math pages are watched like hawks by a bunch of OCD math nerds with no life out-side of the internet. So I find the Wiki math pages quite good. $\endgroup$ – B. Goddard Sep 13 '16 at 15:27

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.