Size of InfinityDate: 07/22/97 at 19:35:59 From: John Cramer Subject: Size of infinity How can one infinity be bigger than another infinity? For example, the number of real numbers between 0 and 1 is infinite. The number of integers greater than 1 is also infinite. Yet the first infinity mentioned is bigger than the second one. I don't get it. Date: 07/25/97 at 17:22:25 From: Doctor Rob Subject: Re: Size of infinity This has puzzled many people over the years. It has to do with the way we count. When you count objects, often you touch (or look at) one of them and say "One." Then you touch another and say "Two." You continue touching previously untouched objects until you run out them. Then the last number you said is the number of objects. In the abstract, what you are doing is setting up a one-to-one correspondence between the objects and a finite set of natural numbers of the form {n | 1 <= n <= N}. It is one-to-one because no number is used twice, and it is a correspondence because no object is used twice. An extension of this can be used to "count" infinite sets. Again a one-to-one correspondence is set up between the set of all natural numbers and the set of objects. If all the objects correspond to a natural number, and all natural numbers correspond to an object, then the set of objects is said to have the same _cardinality_ as the set of natural numbers. The same procedure can be used for any two sets. If they can be put into one-to-one correpondence, then they are said to have the same cardinality. In the case of a finite set, the cardinality is just the number of objects. In the case of infinite sets, one might naively think that all of them would have the same cardinality, and call that "infinity." In fact, there are infinite sets A and B which cannot be put into one-to-one correspondence with each other, but A can be put into one-to-one correspondence with a subset of B. In this case, the cardinality of A is the same as that of the subset of B, but not the same as the cardinality of B. B is said to have larger cardinality than A. Notice that in the case of finite sets, the cardinality of a proper subset of a finite set is always smaller than the cardinality of the whole set, so the analogy is apt. Your example is like that: the natural numbers cannot be put into one-to-one correspondence with the real numbers between 0 and 1, although they can be put into correspondence with a subset (via n <-> 1/(n+1), for example). The hard part is to *prove* that constructing a one-to-one correspondence is impossible in certain cases. That is done by contradiction, by making the assumption that one exists, and from that deducing a false statement. This means that the assumption had to be false to begin with, and the existence is therefore impossible. In this case, suppose there were such a correspondence. Make a table with the first column containing the natural numbers 1, 2, 3, 4, ..., and the second column containing the corresponding real numbers between 0 and 1, written out in decimal expansions. It would take the form: 1 0.*********... 2 0.*********... 3 0.*********... 4 0.*********... ... ... According to the assumption, all real numbers between 0 and 1 will appear in some row in the second column. Now we will construct one which doesn't appear, as follows. Consider the number D beginning "0." and continuing with the digits appearing on the *diagonal* of the array of digits in column 2 of the table. Now pick any number X whose digits *disagree* with D in every decimal place, but which contains no 0 or 9. (There are 7 or 8 choices for each digit of X, so this is easy to do.) Where could it appear on the list? For any natural number k, it cannot be in row k, because its k-th digit differs from the k-th digit of the number appearing in row k. This number is not on the list in any row. As a result, the assumed one-to-one correspondence doesn't exist. Notice that it did not matter in what order we put the numbers in column 2 above, the same construction works. Notice also that there are huge numbers of X's which can be constructed this way: at least 7^k possibilities for just the first k digits to the right of the decimal place; and *none* of them is on the list. (The funny business with 0 and 9 is to avoid the fact that some numbers have two decimal expansions: for example, .500000000... = .499999999... . The constructed X misses both of these representations whenever they exist.) I hope I haven't boggled your mind with this. Mostly it wasn't known until the time of Georg Cantor, in the 19th century. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/