Countability

Date: 09/09/98 at 17:04:51
From: stephanie
Subject: Contest question

How can I show that the rationals are countable and the irrationals are 
uncountable? It seems like so many numbers. Help!

Date: 09/09/98 at 17:56:41
From: Doctor Floor
Subject: Re: Contest question

Hi Stephanie,

To show that rationals are countable, you have to put them in a square 
like this:

     1/1  2/1  3/1  4/1  5/1  ...
     1/2  2/2  3/2  4/2  5/2  ...
     1/3  2/3  3/3  4/3  5/3  ...
     1/4  2/4  4/4  4/4  5/4  ...
     ........

There are double counts. That's no problem, because if the number of 
these is countable, then it certainly is when you have even less. Now 
you can count these in the following way:

     1     2    6    7   15  ....
     3     5    8   14
     4     9   13
    10    12
    11

So you can count all rationals.

Now for the real numbers. Suppose the number of real numbers is 
countable. Let's just write down the real numbers between 0 and 1. You 
can write them down in decimal progression, and in a row, because they 
are countably many. It could start something like this:

    0.23498514750193845019847509845104975...
    0.54394857852398509283450928374509827...
    0.09182560197650921874310298650198473... 
    0.98798452908435435114757183591761251...
    ....

We'll create a new number, digit-for-digit. Now if you take the first 
digit after the dot not being 2, then you have a number unequal to the 
first in the row. If you take the second unequal to 4 then the number 
is also equal to the second number. The third not equal to 1, the 
fourth not equal to 9, etc. If you go on to infinity, you create a real 
number between 0 and 1 and not listed. So you have a contradiction, 
because apparantly the list is not complete - and the number of real 
numbers is not countable.

If you have a math question again, please send it to Dr. Math.

Best regards,

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