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