Uncountable NumbersDate: 10/20/97 at 12:17:24 From: cansever aydin ferit Subject: Uncountability Why are the real numbers between 0 and 1 uncountable? Date: 10/20/97 at 13:13:33 From: Doctor Rob Subject: Re: Uncountability This could be interpreted as a philosophical question, in which case I have no answer. But if you are looking for a mathematical answer, here is one. They are uncountable because any attempt to count them can be proven to fail. Below is a description of how to do that. To count a set is to set up a one-to-one correspondence between an initial segment S of the natural (or "counting") numbers and the elements of the set. This S is a subset of the natural numbers such that if n is in S, and a natural number m < n, then m is in S, too. There is one initial segment for each natural number, consisting of all natural numbers less than or equal to it. They look like: {1}, {1,2}, {1,2,3}, {1,2,3,4}, ... {1,2,3,...,n-1,n}, and so on. There is one additional initial segment, namely the set of all natural numbers. If a set can be counted with one of the former, it is finite, but if you have to use all the natural numbers, it is infinite. In the case at hand, it is clear that the set we want to count is infinite. Suppose there did exist such a one-to-one correspondence. Then write the natural numbers down the first column of a two-column array, and the corresponding real numbers between 0 and 1 down column two, written out as decimal fractions. The array might look like this: n f(n) --- ------------------------- 1 0.46326432846284699919234... 2 0.87236481624123841297674... 3 0.99999421471247192477123... 4 0.10000000000000000000000... = 1/10 5 0.10239487239471923874002... 6 0.18181818181818181818181... = 2/11 7 0.32257876526578634957676... ... ... The claim that this is a one-to-one correspondence means that every real number between 0 and 1 appears somewhere in the second column. We will now demonstrate a number which does not appear in any row in the second column of this array, but is a real number between 0 and 1. We will do that by describing its decimal expansion. For the first digit to the right of the decimal point, pick any digit other than the first digit of the number in row 1, and other than 0 or 9. For the second digit to the right of the decimal place, pick any digit other than the second digit of the number in row 2, and other than 0 or 9. For digit 3, pick any digit other than digit 3 of the 3rd number, and other than 0 and 9. Continue this way. At each step there are at least 7 choices for the digit, so there is never a problem picking one digit from those choices. By avoiding 0 and 9, we not only avoid the real number 0 and the real number 1 = 0.999999..., but we avoid the ambiguity in the decimal system of which this last equation is an example. In the above array, we would pick a number whose first decimal digit was not 0, 4, or 9, whose second decimal digit was not 0, 7, or 9, whose third decimal digit was not 0 or 9, whose fourth decimal digit was not 0 or 9, whose fifth decimal digit was not 0 or 9, whose sixth decimal digit was not 0, 8, or 9, whose seventh decimal digit was not 0, 7, or 9, and so on. For example, we might pick x = .8273318.... Now where in the list is this number we have constructed? If you claim it appears in row n, I can prove it doesn't, since it differs from the number in that row in the nth decimal place (at least!). Furthermore, it really doesn't matter what real numbers occupied what places on this list, we can still perform this construction. The conclusion is that the purported one-to-one correspondence, a map from the natural numbers to the real numbers between 0 and 1, cannot be onto. In fact, there cannot be an onto map from the natural numbers to the real numbers between 0 and 1. Thus this set of real numbers cannot be counted. Such sets are called uncountable. Furthermore, it is pretty obvious that *most* real numbers between 0 and 1 are not on this list, in fact, almost all of them, for any reasonable way of defining what we mean by "most". The first person to use this "diagonal" construction was Georg Kantor, more than 100 years ago. Do you see why the word "diagonal" applies? -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 10/20/97 at 17:50:02 From: AYDIN FERIT CANSEVER Subject: Thanks I received your e-mail and I want to say that it's just the answer that I needed. Thank you so much for your help. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/