Proof:The set of reals is uncountable

Claim (see proof):

The set ℝ of real numbers is uncountable.

Proof:

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.