Associated Topics || Dr. Math Home || Search Dr. Math

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/

Associated Topics:
High School Number Theory
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/