Proof:The set of reals is uncountable

From CS2800 wiki
In fact, we will show that the interval [math]I = [0,1) [/math] of real numbers between 0 and 1 is uncountable. Since [math]I \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math], we can conclude that [math]\href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] is uncountable.

We use diagonalization to prove the claim. Suppose, for the sake of contradiction, that [math]I [/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}{→} I [/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]1/2 [/math]
1 [math]0 [/math]
2 [math]π-3 [/math]
3 [math]0.8989898989\cdots [/math]
4 [math]1/2 [/math]
[math]\vdots [/math] [math]\vdots [/math]

We can put the real numbers [math]f(i) [/math] into a common format by listing out their digits:

i f(i) tenths hundredths thousandths [math]\cdots [/math] [math]\cdots [/math] [math]\cdots [/math]
0 1/2 (5) 0 0 0 0 [math]\cdots [/math]
1 0 0 (0) 0 0 0 [math]\cdots [/math]
2 [math]π-3 [/math] 1 4 (1) 5 9 [math]\cdots [/math]
3 [math]0.8989\cdots [/math] 8 9 8 (9) 8 [math]\cdots [/math]
4 1/2 5 0 0 0 (0) [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]

We construct a new diabolical number [math]x_D [/math] by changing each digit on the diagonal. We can add 5 to each digit (wrapping around if necessary) to set the corresponding digit of [math]x_D [/math]. In example table above, we would have [math]x_D = 0.05645\cdots [/math].

Now, [math]x_D [/math] cannot be in the image of [math]f [/math], because for any [math]k [/math], [math]x_D [/math] differs from [math]f(k) [/math] in the [math]k [/math]th digit. This contradicts the fact that [math]f [/math] is surjective, completing the proof.