Question about Cantor's Diagonal Argument

[Bohandas]

In Cantor's Diagonal Argument to prove that the cardinality of the continuum is greater than that of the rationals, how do we know that the complimentary sequences are all distinct numbers? It's known that they don't contain the same exact sequence as any of the numbers on the list, but there are some numbers that have multiple digital representations (such as 1.0=0.9999...repeating in base 10)

Additionally, in the base 2 version of this argument there naively seems to be only a countably infinite number of diagonals (there's the one at the top left corner of the diagram, then the one starting one down from it, then the one one over from it, then the one starting one over and one down and so on and so on in the same sort of snaking pattern used to put the rationals into bijection with the integers). This would put the total at two times aleph null, which collapses down into being equal to just regular aleph null.

[Khedrac]

For the first I think this is a matter of definition as much as anything else.

You start with a list defined to be all of the members of the set and then construct a member not in the set. It doesn't matter if a member is in the list multiple times because you have just proven that the initial assumption (it is a list of all members of the set) cannot be true which is what implies you are dealing with an uncountable infinity.

As for 1.0000 and 0.9999 recurring - if you are just looking at the numbers between 0 and 1 then 1.0 is not in the set to begin with.

The Binary example just makes this easier to follow - and having proven that you can construct a number not in the set, no attempt to insert it into the list helps - you can still always construct another number not in the set. You are correct that there if the list was countable there would be a countable number of diagonals, but by proving that the list is not countable in the first place then neither is the number of diagonals.

[crayzz]

There's actually a note on that in the wikipedia page:

"While 0.0111... and 0.1000... would be equal if interpreted as binary fractions (destroying injectivity), they are different when interpreted as decimal fractions, as is done by f. On the other hand, since t is a binary string, the equality 0.0999... = 0.1000... of decimal fractions is not relevant here."

In other words, its a matter of constructing representations that can't point to the same number.

[DavidSh]

As for 1.0000 and 0.9999 recurring - if you are just looking at the numbers between 0 and 1 then 1.0 is not in the set to begin with.

It's a little more involved than this. The same issue shows up with 0.010000... and 0.0099999... . But each real number has at most two representations as an infinite sequence of digits ( and incidentally, the set of numbers with two such representations is countable ). The proof by contradiction could work as follows:

Choose your base.
Every infinite sequence of digits corresponds to a real number in [0, 1).
Every real number corresponds to at most two infinite sequences of digits.

Suppose the set of real numbers were countable.
Then we could enumerate them in a list.
Then we could enumerate their representations as infinite sequences of digits in a list, using the same order, but placing the two representations of those numbers having them one after the other.
But we can construct the diagonal, and generate an infinite sequence of digits that isn't on this list.
Then this new sequence of digits corresponds to a real number not in the original list.
XXX a contradiction XXX

[PirateMonk]

We can prove fairly easily that in fact the only case where two infinite decimals represent the same number are if one ends in ...999999... and ones ends in ...00000...:

Let a and b be two different decimal representations. Let n be the first decimal place where they have different digits; we can assume that a_n (the nth digit of a) is greater than b_n (the nth digit of b). Then if we cut off a and b at the nth decimal place, the truncation of a will be at least 10^-n greater than the truncation of b, so the digits of a and b after the nth place must make up this difference if they are to be equal. The best we can do in making up the difference is if all remaining digits of b are 9 and all remaining digits of a are 0. In this case, since the sum from k=n+1 to infinity of 9*10^-k is 10^-n, we will exactly make up the difference, as long as a_n is just b_n+1. If the nth digits differ by more than 1, or if any of the subsequent digits of a are not 0 or any of the subsequent digits of b are not 9, it will be completely impossible to make up the difference, so a and b will represent different numbers.

This resolves any concerns about applying the diagonal argument to real numbers in multiple ways:
1. By being careful about how we construct the new number, we can ensure that none of the digits are 0 or 9. This means that it will represent a number with a unique representation, so the fact that the representation is different from all representations on our list implies that the number it represents is different from all representations on our list.
2. Since every real number has one or two representations, in particular no real number has uncountably many representations. Because the diagonal argument shows there are uncountably many representations, this implies that there must also be uncountably many numbers.
3. Since every real number with two representations has a representation which ends in infinitely many zeros, every such number is a rational number (and can be written with denominator a power of ten). This means there can only be countably many such numbers, so they are easy to work around (although now that I think about it, most strategies for working around them will basically boil down to one of the previous two options).