Hacker News Reader

Comment by shenberg | Hacker News Reader

One point I never see discussed in these things is that you need to take a bit of care with digit-based representations because 0.1111... = 1.000..., 0.0111.... = 0.1000... - an argument could be made that perhaps while you know the number you're constructing via diagonalization doesn't appear in the list of numbers you created, but it may be a different representation of a number that does appear in the list.

The simplest way I know to work around that is by excluding numbers ending in infinite strings of 0s or 1s from the list. Anyone know a nicer way?

View on HN

The ambiguity in digit representations only comes from numbers ending in 1's (in base 2, or ending in 9's in base 10). If you do the argument in a different base than 2 you can avoid the problem: you can construct a number whose base 10 representation consists only of 5's and 6's and which is different from any number in the list.

A careful argument will thus often deal with ternary representations, and always choose the 'ternit' 0 or 1 that is different from the 'ternit' under consideration. It's a bit less elegant than dealing with binary representations, but it does avoid the difficulty you mention.

The usual way this is done is by selecting a canonical representation for the reals in the list. It's pretty much the same thing as you said, but I don't think you're putting it in the right terms.

The list you're diagonalising (in Cantor's diagonal argument that the reals are uncountable) is a list of real numbers. Each of those reals has a canonical representation, and the reals in the list are ordered according to an order defined on those representations. The argument then demonstrates a method of constructing from those representations a representation of a new real which, by definition, cannot be one of the reals in that list.

Put in those terms it feels a lot less arbitrary than simply excluding certain strings.

Problem there is that you then have to prove that the string you've constructed is in your canonical form, and it might not be.

Reply on news.ycombinator.com