Prove that the set of real numbers in the interval [0, 1] is uncountable. hint: use the diagonalization argument on the decimal expansion of real numbers.

We can take a small twist of Matt N.'s hint to make sure we don't run into trouble with dual representations. To see what the problem is, note that, for example, there are two ways of writing 12 in binary:

0.100000…and0.011111…

Step-by-step explanation:

n principle, it would be that your list begins with 0.1000…, and then the numbers in position n all have nth digit equal to 0 for all n>1. Then the straight "change the digit" process leads to 0.01111…, which is on the list (it's a different representation of the first number on the list).

So the first thing we need to do is specify that we will use one particular representation in our "list"; usually the one that terminates if there is a choice.

That done, instead of looking at the single diagonal digit, work with diagonals in blocks of 2; that is, look at the digits in position 1 and 2 first, then the digits in positions 3 and 4 for the second number, and so on, looking at the digits in position 2k+1 and 2k+2 for the kth number. Then make the "switch" ensuring that the number you construct does not have two different representations. For instance, if the kth number in the list has 00, 01, or 11 in the 2k+1 and 2k+2 positions, then put 10 in your number on those positions; if the kth number in the list has 10, then put 01 on your list. Then the number you construct does not have two representations, so you can test that it is not on the list by simply comparing the 2k+1 and 2k+2 digits with the kth number on the list.

So if your list looks like:

0.a11a12a13a14a15a16⋯a1,2k+1a1,2k+2⋯

0.a21a22a23a24a25a26⋯a2,2k+1a2,2k+2⋯

0.a31a32a33a34a35a36⋯a3,2k+1a3,2k+2⋯

⋮

0.ak1ak2ak3ak4ak5ak6⋯ak,2k+1ak,2k+2⋯

⋮

You then take each red block and construct a new number

0.b1b2b3b4b5b6⋯b2k+1b2k+2

where b1b2 is chosen so that it is different from a11a12; b3b4 is chosen so that it is different from a23a24; b5b6 is chosen so that it is different from a35a36;…,b2k+1b2k+2 is chosen so that it is different from ak,2k+1a2k+2, etc. So you are "going down the diagonal" and changing things so that the resulting number is not on the list: it's not the first number on the list, because it differs from it in the first two entries and your number has only one representation. It's not the second number on the list because it differs from that one in the third and fourth digits; given any k, the number constructed is not the kth number on the list because it differs from it in the 2k+1 and 2k+2 positions. Etc.

Just for your awareness, here is an ALTERNATIVE WAY to show it.

Look at [0,1] as a metric space (a subspace of R with the usual Euclidean distance). It is complete since R is complete and [0,1] is closed. But we may write

[0,1]=⋃x∈[0,1]{x}.

Singletons are closed and have empty interior, so it follows that [0,1] must be uncountable, otherwise this would contradict the Baire Category Theorem. From here, we have that (0,1) is obtained by removing two elements from an uncountable set, and so (0,1) is uncountable.