Uncountable Numbers

Date: 10/20/97 at 12:17:24
From: cansever aydin ferit
Subject: Uncountability

Why are the real numbers between 0 and 1 uncountable?

Date: 10/20/97 at 13:13:33
From: Doctor Rob
Subject: Re: Uncountability

This could be interpreted as a philosophical question, in which case I 
have no answer. But if you are looking for a mathematical answer, here 
is one.

They are uncountable because any attempt to count them can be proven 
to fail. Below is a description of how to do that.

To count a set is to set up a one-to-one correspondence between an 
initial segment S of the natural (or "counting") numbers and the 
elements of the set. This S is a subset of the natural numbers such 
that if n is in S, and a natural number m < n, then m is in S, too.  

There is one initial segment for each natural number, consisting of 
all natural numbers less than or equal to it.  They look like:  
{1}, {1,2}, {1,2,3}, {1,2,3,4}, ... {1,2,3,...,n-1,n}, and so on.  

There is one additional initial segment, namely the set of all natural 
numbers. If a set can be counted with one of the former, it is finite, 
but if you have to use all the natural numbers, it is infinite.  In 
the case at hand, it is clear that the set we want to count is 
infinite.

Suppose there did exist such a one-to-one correspondence.  Then write 
the natural numbers down the first column of a two-column array, and 
the corresponding real numbers between 0 and 1 down column two, 
written out as decimal fractions.  The array might look like this:

  n     f(n)
 ---   -------------------------
  1    0.46326432846284699919234...
  2    0.87236481624123841297674...
  3    0.99999421471247192477123...
  4    0.10000000000000000000000... = 1/10
  5    0.10239487239471923874002...
  6    0.18181818181818181818181... = 2/11
  7    0.32257876526578634957676...
 ...   ...

The claim that this is a one-to-one correspondence means that every 
real number between 0 and 1 appears somewhere in the second column.  
We will now demonstrate a number which does not appear in any row in 
the second column of this array, but is a real number between 0 and 1.  
We will do that by describing its decimal expansion.

For the first digit to the right of the decimal point, pick any digit 
other than the first digit of the number in row 1, and other than 0 
or 9. For the second digit to the right of the decimal place, pick any 
digit other than the second digit of the number in row 2, and other 
than 0 or 9. For digit 3, pick any digit other than digit 3 of the 3rd 
number, and other than 0 and 9. Continue this way. At each step there 
are at least 7 choices for the digit, so there is never a problem 
picking one digit from those choices. By avoiding 0 and 9, we not only 
avoid the real number 0 and the real number 1 = 0.999999..., but we 
avoid the ambiguity in the decimal system of which this last equation 
is an example.

In the above array, we would pick a number whose first decimal digit 
was not 0, 4, or 9, whose second decimal digit was not 0, 7, or 9, 
whose third decimal digit was not 0 or 9, whose fourth decimal digit 
was not 0 or 9, whose fifth decimal digit was not 0 or 9, whose sixth 
decimal digit was not 0, 8, or 9, whose seventh decimal digit was not 
0, 7, or 9, and so on.  For example, we might pick x = .8273318....

Now where in the list is this number we have constructed? If you claim 
it appears in row n, I can prove it doesn't, since it differs from the 
number in that row in the nth decimal place (at least!). Furthermore, 
it really doesn't matter what real numbers occupied what places on 
this list, we can still perform this construction. The conclusion is 
that the purported one-to-one correspondence, a map from the natural 
numbers to the real numbers between 0 and 1, cannot be onto. In fact, 
there cannot be an onto map from the natural numbers to the real 
numbers between 0 and 1. Thus this set of real numbers cannot be 
counted.  Such sets are called uncountable.

Furthermore, it is pretty obvious that *most* real numbers between 0 
and 1 are not on this list, in fact, almost all of them, for any 
reasonable way of defining what we mean by "most".

The first person to use this "diagonal" construction was Georg Kantor, 
more than 100 years ago.  Do you see why the word "diagonal" applies?

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 10/20/97 at 17:50:02
From: AYDIN FERIT CANSEVER
Subject: Thanks

I received your e-mail and I want to say that it's just the answer 
that I needed.  Thank you so much for your help.