# Proof:The set of reals is uncountable

The set of real numbers is uncountable.
Proof:
In fact, we will show that the interval of real numbers between 0 and 1 is uncountable. Since , we can conclude that is uncountable.

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

i f(i)
0
1
2
3
4

We can put the real numbers into a common format by listing out their digits:

i f(i) tenths hundredths thousandths
0 1/2 (5) 0 0 0 0
1 0 0 (0) 0 0 0
2 1 4 (1) 5 9
3 8 9 8 (9) 8
4 1/2 5 0 0 0 (0)

We construct a new diabolical number by changing each digit on the diagonal. We can add 5 to each digit (wrapping around if necessary) to set the corresponding digit of . In example table above, we would have .

Now, cannot be in the image of , because for any , differs from in the th digit. This contradicts the fact that is surjective, completing the proof.