From the excellent appendix to Wesley Salmon’s Zeno’s Paradoxes (Bobbs-Merrill, 1970), p. 258ff:
[My emphasis; formatting won’t allow as much space as I’d like between the list of naturals on the left and the list of reals on the right.]
Salmon leaves as a question for the reader why we always choose a digit other than zero, but I’m not smart enough to figure it out.
So, why?
I can give you 0.9999… good reasons to avoid using 0 as a digit.
Presumably so that the hypothetical not-in-the-list number is not 0 .
(Also, a tangential spoiler alert for those who aren’t familiar with the proof: you keep going down that list, choosing digits differing from zero (apparently) and the nth digit, where n is the natural number on the left. String these all together behind an initial zero and you get a number that can’t be on the list–for every n, it’s different from that number at the nth place. Therefore there aren’t enough numbers to count all the numbers, therefore mind blown.)
I have not read that book, but I hope the author proves that the only way a real number cannot be uniquely expressed as a decimal is if it ends in an infinite string of zeros or nines. Then, you need to deal with that one way or the other.
To be clear, any terminating decimal can be expressed as:
0.d[sub]1[/sub]d[sub]2[/sub]d[sub]3[/sub]…d[sub]n-1[/sub]d[sub]n[/sub]000000000…
or as:
0.d[sub]1[/sub]d[sub]2[/sub]d[sub]3[/sub]…d[sub]n-1/sub999999999…
Where d[sub]i[/sub] are the non-zero digits.
If we allowed either to be picked, Cantor’s argument would fail because we could say, “the diagonal number is not in the list in that form, but maybe it is actually in the list in its other form”. Requiring zero to never be picked ensures that we only get the latter form of each number.
Fixed.
One way to avoid the bother of problems like 0.400000 = 0.3999999… in proofs like this is to use a representation of the reals which guarantees uniqueness. For example, Continued fractions provide a unique mapping between the real segment (0,1] and sequences of natural numbers (finite or infinite sequences for rationals or irrationals resp.). Other examples?
I once worked thru doing Cantor’s proof using base 2 (I’m a Computer Scientist).
So picking a different digit is forced, there’s only one other option.
The .1111… problem is an issue that has to be handled separately. But I see nothing wrong with picking zero here and there. And if you end up always picking zero since there’s a 1 in the nth spot of the nth number and end up with 0, then the list must not include 0 which violates the condition.
As far as unique representations of all numbers in [0,1) there’s the Stern-Brocot tree. (Which of course is a continued fraction thing in another form.) Note that the irrational numbers are merely infinite paths in the tree. Something the Wikipedia article doesn’t point out.*
So numbers are encoded using L, R paths (why the article uses “H” instead of “R” is beyond me). And you can do diagonalization, swapping L and R, but the extra complication are the finite paths with no “zero” in the notation.**
** You merely ignore it and go on to the next one. Clearly any such skipped finitely long number will not be the same infinitely long number you end up with.
Without looking at it, I’d guess if comes from a horizontal rather than vertical tree. Then H and L stand for High and Low rather than Right and Left.
It’s been 30 years since I studied this subject, and I had completely forgotten the need to avoid numbers with dual representation; I also had never known that continued fractions were unique, so thanks!
Like ftg’s post above, Cantor’s original publication (referred to by Wikipedia’s version), does not use choosing, and he uses 2 symbols in his example. However Cantor does not talk about “constructing a real number not on the list”, he talks about coordinates, functions, and contradiction. I think Cantor avoids the problem with cases like 0.1000… = 0.0111… (in binary) by the higher abstraction level in his publication; I confess not completely understanding it.
I’m afraid I was (slightly?) wrong! :o Each rational number has two cf forms (one which ends in ‘1’ and one which doesn’t):
4/5 = [1,4] = [1,3,1]
This can be fixed with a slight jiggle: Subtract 1 from the final term in a finite cf. (Jiggles to cope with the 0.400000 = 0.39999999… problem are less trivial.)