Proof:The power set of the naturals is uncountable
|2||the set of even numbers|
|3||the set of odd numbers|
|2||the set of even numbers||yes||no||(yes)||no||yes|
|3||the set of odd numbers||no||yes||no||(yes)||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
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.