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?