# Proof:The power set of the naturals is uncountable

is uncountable.
Proof:
We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that is countable. Then there exists a surjection .

We can imagine drawing as a table. For example, the first few outputs of might look like this:

i f(i)
0
1
2 the set of even numbers
3 the set of odd numbers
4

To put the sets into a common format, we might expand each set as a sequence of yes/no questions, with the th column of indicating whether :

i f(i)
0 (yes) yes yes yes yes
1 no (no) no no no
2 the set of even numbers yes no (yes) no yes
3 the set of odd numbers no yes no (yes) no
4 yes no no no (no)

Now, we construct a new diabolical set by changing each element on the diagonal. In this example, we have a "yes" in the 0th column of row 0 (meaning , so in our diabolical set we put a "no" in column 0 (by ensuring . Similarly, we have a "no" in row 1, column 1 (so ), so we put a "yes" in column 1 of (by placing ). Continuing in this fashion, we have

no yes no no yes

In general, we include if and only if . We can write this succinctly by defining . Note that although we used a specific example to figure out how to construct , this construction will work for an arbitrary .

Now, cannot be in the image of , because for any , differs from in the th column. If then , and if then . in either case, . Thus cannot be surjective, a contradiction.