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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.