The set of real numbers isn't countable (Cantor's diagonal argument)

xinta (55)in #mathematics • 7 years ago (edited)

The set of real numbers is not countable. That is, it doesn't exist a bijection between it and the set of natural numbers. Does it sound hard? Maybe it is, if you don't know a thing about what a set is and what real and natural numbers are…

Here I don't want to explain those, but I want instead to show that the proof is easy. This one fascinates me alot because of this: the proof is easy, and brilliant, and also more brilliant because easy. Easy to the point that you can appreciate it even if you don't know anything — almost — about sets, numbers…

The proof is the Cantor's diagonal argument.

First of all, let us consider only the numbers in the interval [0,1]. How many real numbers are inside that interval? An infinite number. Let's take a list:

0.7841937333…
0.1223441111…
0.3343194383…
0.0039482321…
0.9876544432…
0.1234555678…
0.1233456777…
0.0123298876…
0.1233454321…
0.8898766656…
…

Of course you need infinite time and space to write all those numbers. So let's stop there. We have shown 10, the three dots on the last line make us remember that there's more. And the three dots at the end of each line make us remember that each of those numbers is made of an infinite number of digits.

That infinite list contains all the number in the interval [0,1]. Trust me, I've counted them!

Now the Cantor's argument is this: let's build a number made of the number of the diagonal (highlighted in bold): 0.7249556826… This is a number made of an infinite number of digits, too, but let's stop somewhere before the end of the Universe.

Now, let's change the digits; for example let's add one to each digit (no carry, of course): 0.8350667937… This made-up number does not exist in the list, even if allegedly the list contained all the numbers between 0 and 1!

Why? Because it surely differs from the first number in the first digits, differs from the second number in the second digit, from the third number in the third digit… And so on: we've built a number for which we can also be sure that it differs from every number in the infinite list for at least a single digit!

What does it mean? It means that the set of real numbers isn't countable. It means that in the interval [0, 1] there's a number of (real) numbers “more infinite” than the infinite of the number of natural numbers. That is, it exists an “infinite” which is bigger than another “infinite” (the “infinite” of the set of the natural numbers).

This is not a correct mathematical wording, but I hope it gives you an idea of the wonderful concepts involved.