There are more real numbers than natural numbers

The natural numbers are the numbers 1, 2, 3, 4, … . Real numbers are numbers such as 10.4541, 3.14, -2358.541, etc., etc.

Obviously, there is an infinite number of natural numbers. No matter what natural number I name, you can name one that’s bigger. And likewise, obviously there is an infinite number of real numbers.

Nevertheless, there are more real numbers than natural numbers!

That means that (i) there is more than one infinity and that (ii) some infinities are bigger than other infinities. As astonishing as that may seem, Cantor’s diagonalization argument proves it.

Consider any function whose input is a natural number and whose output is a real number between 0 and 1. Call the function “f”. Now, let’s write a table for f:

n           f(n)
–            —-
1           0.889579989…
2           0.434358948…
3           0.548985443…
4           0.323298545…
5           0.625985948…
6           0.785354389…
…      …

The table displays the value of f for each natural number. So, for example, the first entry states that f(1) = 0.889579989…

A “…” at the end of a value of f(n) signals that the value of f(n) is an infinitely long decimal. We can treat each real number between 0 and 1 as an infinitely long decimal, without loss of generality. For example, if we have 0.5, then we simply write 0.500000000… .

The specific values of f don’t matter, because we are considering any function from the natural numbers to [0, 1]. I just made up some values for illustrative purposes.

You’ll notice that I’ve bolded some of the digits in the table. Let’s construct a number from those digits.

Doing that, we obtain 0.838284… . Now, let’s add 1 to each digit of 0.838284… . Of course, we get 0.949395… .

Surprisingly, 0.949395… cannot possibly be in the table!

0.949395… can’t be equal to f(1), because it differs from f(1) in its first digit. Likewise, it can’t be equal to f(2), because it differs from f(2) in its second digit. And in general, 0.949395… can’t be equal to f(n), because it differs from f(n) in its nth digit.

So, no matter what natural number you put into the function, there will be a real number that you can’t get out. So, there are more real numbers than natural numbers!

In mathematical jargon, the real numbers are uncountably infinite.

But what does it mean to say that a set is “uncountable”?

To see that, consider what you’re actually doing when you count something. If you will, start counting the keys on your keyboard. When you look or point at the first key, you say or think, “1.” When you look or point at the second key, you say or think, “2.” And so on.

In other words, you are associating natural numbers with members of a set (i.e., the set of keys). You’re done counting when you’ve associated each key with one (and only one) natural number.

But, as we’ve seen, you can’t do that with the real numbers. Even if you could go through all the natural numbers, there would be real numbers that you couldn’t associate a natural number with. So, the real numbers are uncountable.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s