Infinite Sets

Date: 07/17/97 at 10:23:01
From: Bob
Subject: Infinite sets

How do you prove that there are more rational numbers than negative 
integers?

How can you tell if an infinite set is countable or uncountable?

I know that the number of rational numbers and negative integers is 
the same, but I can't prove it.

Also, I am confused by the countable/uncountable quality of infinite 
sets.  

Please answer these questions.
Bob

Date: 08/06/97 at 01:00:56
From: Doctor Dan
Subject: Re: Infinite sets

Bob,

You've asked a very interesting question.  

It is only within the last one hundred years of so that people have 
developed ways to think clearly about infinite sets. We owe much of 
the clarity of our thought to Georg Cantor.  His central insight was 
to examine whether or not two sets could be put in one-to-one 
correspondence. If you can establish such a correspondence, then the 
sets are said to have the same cardinality (they have the same 
[infinite] "number" of elements).

Imagine that you are trying to determine whether or not two large 
groups of people are the same size. One possible procedure would 
be to line up each group. Then you could pair the first person in 
one line with the first person in the second; the second person in the 
first line with the second person in the second line; etc. Once all 
the pairs are made, it will be easy to see whether one of the groups 
has any folks left over. If so, that group will have a greater number 
of elements.  

There is an important point in this scheme: the people do not need to 
line up in any particular order; we just need to make sure that 
everyone is in fact in the line somewhere.

Now let's think about the rational numbers.  Can we "line them up?"  
We cannot line them up by size (since between any two we can always 
find a third rational number larger than the first yet smaller than 
the second). But what if we group them by denominators? 

We'll start our line-up with those rational numbers that have 2 as a 
denominator, listing them in ascending order of their numerators.  
There is only one such number: 1/2.  

Then we'll list those that have 3 as a denominator. There are two of 
these: 1/3 and 2/3. Next we take the group with 4 as a denominator: 
1/4, 2/4, and 3/4. (We can discard 2/4 from our list since we've 
already used it in simplified form.)  

If we continue in this way every rational number will eventually be 
included, even though our list will be infinitely long. For 
example, 24/61 will be right after 23/61 and right before 25/61.  
Also, 1/3209 will be immediately following 3207/3208. Every rational 
number will have a clearly defined place in line.

This list of rational numbers can be paired off with the list of 
negative integers. Even though both lists are infinite, we can see 
that every rational number will be included in our listing and will, 
eventually, be paired with a negative integer. Also, every negative 
integer will eventually be paired with a rational number. There are no 
rational numbers or negative integers that fail to be in our lists and 
consequently fail to be paired.  

The ability to pair the elements of an infinite set with the 
counting numbers is what we mean when we say that a set is countable. 
It means that we can construct a means of listing all the elements of 
the set such that there is a "first" element, a "second" element, a 
"third" element, etc.

An infinite set is said to be uncountable if it is not possible to 
establish a method of listing every element. One of Cantor's more 
ingenious achievements was his "diagonal proof" that the real numbers 
were uncountable. He showed that no matter how cleverly you 
constructed a list of real numbers, it was possible to name a real 
number that was not in your list. Thus it was not possible to list all 
the real numbers; the infinite set of real numbers is uncountable.

NOTE: You're probably thinking that my scheme for ordering the 
rational numbers only covers those between 0 and 1. Well, you're 
correct. I chose to sequence that group as a way of illustrating how 
an infinte set can be ordered to make it countable.  It is possible to 
list all the rational numbers in an ordered sequence.  Write them down 
in this array:

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

Now list the numbers "on the diagonal," i.e. 

          1, 
          1/2, -1, 
          1/3, -1/2, 2, 
          1/4, -1/3, 2/2, -2, 
          1/5, -1/4, 2/3, -2/2, 3,  
          1/6, -1/5, 2/4, -2/3, 3/2, -3, .... 

Discard the equivalent fractions and add zero to the head of the 
list and we still have a well-defined list whose elements can be 
paired with the counting number. Thus the rationals are countable, or 
"denumerable" as Cantor would have said.) 

It is obviously not an easy task to determine whether an infinite 
set is countable or not.  It is a matter of whether you have enough 
ingenuity to devise a scheme for listing all the elements of the set.

I hope that my attempt at an answer to your question has been 
of some help in your efforts to understand infinite sets.

William Dunham has an excellent, and not too difficult, chapter on 
this topic in his fine book "Journey Through Genius," 1990, Penguin.

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