(no title)
owalt | 2 years ago
It's maybe easier to think of the argument as working on sequences: From a sequence (x_0, x_1, x_2, ...) with each x_n a binary digit (i.e. 0 or 1) you can always construct a real number x = Sum(x_n / 2^n, n = 0, 1, 2, ...).
The integer you'd want to construct from such a sequence would be Sum(x_n * 2^n, n = 0, 1, 2, ...), but this only works if there's some N such that x_n = 0 for all n > N. Otherwise you would have an "infinite integer" (whatever that means). Valid positive integers are all on the form Sum(x_n * 2^n, n = 0, 1, 2, ..., N), i.e. the binary expansion is finite.
The subtlety of the diagonal argument (why it works for reals but not for integers/rationals) is that while it always produces _some_ string of digits, only the real numbers are defined such that the string of digits is itself always a real number. In the integer/rational case, you can construct a number "outside" the set you started from. (In fact you always do if the original list really was of all integers/rationals. Given any enumeration of the rationals, the diagonal argument can actually be used constructively to produce an irrational number.)
No comments yet.