- #1
Warp
- 128
- 13
Thinking about Cantor's diagonal argument, I realized that there's another thing that it proves besides the set of all infinite strings being uncountable.
Namely: That it's not possible to list all rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence.
My logic goes like this: It's possible to list all rational numbers in order without repetitions, for example using the Calkin-Wilf sequence. However, let's assume that you could list all rational numbers in such an order that the diagonal of their decimal expansion formed an infinitely repeating sequence. Let's say, for example, the sequence 0123456789, like:
0.0xxxxxx...
0.x1xxxxx...
0.xx2xxxx...
and so on. However, if we now apply the diagonal argument and take those digits in the diagonal and eg. increment each of them (with 9 wrapping around to 0), we would get a number that has an infinitely repeating decimal sequence, which is rational, but which is different from all the numbers in the list. Which contradicts the premise that the list contained all the rational numbers.
Since we know that every number with an infinitely repeating decimal sequence is a rational number, the only possible conclusion is that it's not possible to list all the rational numbers in an order such that their diagonal forms a repeating sequence (even if that repeating sequence has all the digits).
However, it's not at all intuitive to me why that's not possible.
(It's very obvious that you cannot list them so that the repeating sequence lacks one of the digits, because then the rational numbers whose decimal expansion does not have said digit wouldn't fit anywhere. It's much less obvious if the sequence has all the digits, eg. 0123456789.)
Namely: That it's not possible to list all rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence.
My logic goes like this: It's possible to list all rational numbers in order without repetitions, for example using the Calkin-Wilf sequence. However, let's assume that you could list all rational numbers in such an order that the diagonal of their decimal expansion formed an infinitely repeating sequence. Let's say, for example, the sequence 0123456789, like:
0.0xxxxxx...
0.x1xxxxx...
0.xx2xxxx...
and so on. However, if we now apply the diagonal argument and take those digits in the diagonal and eg. increment each of them (with 9 wrapping around to 0), we would get a number that has an infinitely repeating decimal sequence, which is rational, but which is different from all the numbers in the list. Which contradicts the premise that the list contained all the rational numbers.
Since we know that every number with an infinitely repeating decimal sequence is a rational number, the only possible conclusion is that it's not possible to list all the rational numbers in an order such that their diagonal forms a repeating sequence (even if that repeating sequence has all the digits).
However, it's not at all intuitive to me why that's not possible.
(It's very obvious that you cannot list them so that the repeating sequence lacks one of the digits, because then the rational numbers whose decimal expansion does not have said digit wouldn't fit anywhere. It's much less obvious if the sequence has all the digits, eg. 0123456789.)