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

### Uncountable Numbers

```
Date: 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

that I needed.  Thank you so much for your help.
```
Associated Topics:
High School Number Theory

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