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 [math]f [/math] as a table. For example, the first few outputs of [math]f [/math] might look like this:

i	f(i)
0
1
2	the set of even numbers
3	the set of odd numbers
4
[math]\vdots [/math]	[math]\vdots [/math]

To put the sets [math]f(i) [/math] into a common format, we might expand each set as a sequence of yes/no questions, with the [math]j [/math]th column of [math]f(i) [/math] indicating whether :

i	f(i)						[math]\cdots [/math]
0		(yes)	yes	yes	yes	yes	[math]\cdots [/math]
1		no	(no)	no	no	no	[math]\cdots [/math]
2	the set of even numbers	yes	no	(yes)	no	yes	[math]\cdots [/math]
3	the set of odd numbers	no	yes	no	(yes)	no	[math]\cdots [/math]
4		yes	no	no	no	(no)	[math]\cdots [/math]
[math]\vdots [/math]	[math]\vdots [/math]	[math]\vdots [/math]	[math]\vdots [/math]	[math]\vdots [/math]	[math]\vdots [/math]	[math]\vdots [/math]	[math]\ddots [/math]

Now, we construct a new diabolical set [math]S_D [/math] 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 [math]S_D [/math] (by placing ). Continuing in this fashion, we have

						[math]\cdots [/math]
[math]S_D [/math]	no	yes	no	no	yes	[math]\cdots [/math]

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 [math]S_D [/math], this construction will work for an arbitrary [math]f [/math].

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.