Proof:The power set of the naturals is uncountable

From CS2800 wiki
[math]\href{/cs2800/wiki/index.php/2}{2}^{\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}} [/math] is uncountable.
Proof:
We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that [math]\href{/cs2800/wiki/index.php/2}{2}^\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] is countable. Then there exists a surjection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/2}{2}^{\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}} [/math].


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 [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]
1 [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math]
2 the set of even numbers
3 the set of odd numbers
4 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math]
[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 [math]j \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i) [/math]:

i f(i) [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]\cdots [/math]
0 [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] (yes) yes yes yes yes [math]\cdots [/math]
1 [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] 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 [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} [/math] 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 [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(0) [/math], so in our diabolical set we put a "no" in column 0 (by ensuring [math]0 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} S_D [/math]. Similarly, we have a "no" in row 1, column 1 (so [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(1) [/math]), so we put a "yes" in column 1 of [math]S_D [/math] (by placing [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} S_D [/math]). Continuing in this fashion, we have

[math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(i)? [/math] [math]\cdots [/math]
[math]S_D [/math] no yes no no yes [math]\cdots [/math]


In general, we include [math]i \href{/cs2800/wiki/index.php/%E2%88%88}{∈} S_D [/math] if and only if [math]i \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(i) [/math]. We can write this succinctly by defining [math]S_D \href{/cs2800/wiki/index.php/Definition}{:=} \{i \href{/cs2800/wiki/index.php/%5Cmid}{\mid} i \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(i)\} [/math]. 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, [math]S_D [/math] cannot be in the image of [math]f [/math], because for any [math]k [/math], [math]S_D [/math] differs from [math]f(k) [/math] in the [math]k [/math]th column. If [math]k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} f(k) [/math] then [math]k \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} S_D [/math], and if [math]k \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} f(k) [/math] then [math]k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} S_D [/math]. in either case, [math]S_D \href{/cs2800/wiki/index.php/Equality_(sets)}{≠} f(k) [/math]. Thus [math]f [/math] cannot be surjective, a contradiction.