scott <sco### [at] scottcom> wrote:
> > Integers are allowed to have infinite digits before the decimal place.
> > Reals are allowed them after the decimal place as well. ;-)

> Genuine question then, why isn't the set of real numbers countable, 
> given that you could represent each one with two integers (one for the 
> digits before the decimal point, one for the digits after the decimal 
> point)?

The set of all strings that contain all possible combinations of two
or more digits (in other words, the set of all possible decimal
representations) is uncountable. In other words, it's not possible to
enumerate them all. This might be a bit surprising (it was to me...)

Cantor's diagonal argument is used to demonstrate this. Note, though,
that said argument only proves that there are sets that are uncountable
(ie. cannot be enumerated with integers), not that the set of reals is
uncountable.

Cantor's diagonal argument is a proof by contradiction. It goes something
like this:

Let's assume that it is possible to enumerate every single possible infinite
string of digits. Thus we have a(n infinite) list of numbered strings (its
order doesn't really matter, as long as it contains *all* of them.) For
example like:

1: 1001101110...
2: 0010110111...
3: 1100011110...
4: 0111001101...
...

If the assumption is true, that means that this list is complete, ie. it
contains every single possible string using those two digits. Which would
mean that it's impossible to construct a string that does not appear in
that list.

However, we can construct such a string: Take the first digit of the first
string and invert it, the second digit of the second string and invert it,
and so on. In other words, with the example above the string would be
0110... etc.

Said string is different from every single one in that list (because it
necessarily differs from each one by at least one of the digits.) This is
a contradiction because the list was supposed to contain *all* of them.
(It doesn't help if you just "add" this new string to the list. You can
then construct another string that's not in the list.)

Because this is a contradiction, the initial premise is necessarily false:
It's *not* possible to enumerate all of those strings. Therefore the set
of all those strings is genuinely larger than the set of integers.

(But as said, AFAIK this only proves that the set of all possible strings
of two digits is larger than the set of integers, it doesn't yet prove
that the set of real numbers is also. However, it's probably getting there,
and may only require a few steps more to prove also that.)

-- 
                                                          - Warp

Post a reply to this message