Sets Containing an Infinite Number of Members

Date: 02/03/98 at 19:33:30
From: Kate
Subject: Sets Containing an Infinite No. of Members

Which of these 2 sets is larger?

A. The set of all rational numbers
B. The set of all irrational numbers

Date: 02/06/98 at 10:56:10
From: Doctor Celko
Subject: Re: Sets Containing an Infinite No. of Members

The set of irrational numbers is larger, but it is harder to find them
than it is to find rational numbers. 

The way that you prove one set is the same size as another is to map 
each element of set A onto one element of set B; this is really a 
fancy version of a caveman matching his arrowheads to his seashells to 
see if he has more of one thing than another.

The rational numbers can be matched to the integers using a trick 
called Cantor's diagonalization. Make an infinite table of the 
rational numbers (p/q):

    1/1    1/2   1/3 ...
    2/1    2/2   2/3 ...
    3/1 ...
    ...

Rows are increasing values of q and the columns are increasing values 
of p. 

You can dance down this table by starting at 1/1, then go to 1/2, to 
2/1, to 3/1 and back up the diagonal. You can repeat this pattern up 
and down all the diagonals of the table forever, counting the (p/q) as 
you go.

With irrational numbers, assume that you can make a countable list of 
them as infinitely long decimal fractions and make each row of the 
list unique:

   .0218498756985 ...
   .1849875698598 ...
   .98756985785899...
   ...

Look down the diagonal of this list (.087...) and you will see an 
infinite decimal fraction. Change all the digits in this fraction to 
something else and you will have a number that cannot be in the list 
because it is different from the n-th number of the list in the n-th 
position. So this set must be bigger than the set of countable 
numbers.

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