When the Shortest Path is the Diagonal
A short yet rigorous explanation of the most fascinating demonstration technique in Math
Hello, Hypers!
We’re back for another Tuesday. I’m very excited about today’s article. I’m going to talk about Cantor’s Diagonal Argument.
If you have been here for a while, you are already familiar with Georg Cantor. Two weeks ago, we discussed his tragic life and fascinating results. If you missed it, don’t worry: here it is.
In that article, we talked about how Cantor discovered that there are infinite kinds of infinities and proved the so-called Cantor’s Theorem. But the results of Cantor and my fascination for them are far from over.
Today we are going to introduce what I think is his major contribution to Math: the Cantor’s Diagonal Argument. This is a quite particular demonstration technique that allowed him and many of his successors to prove many mind-blowing results.
The Diagonal Argument is not new for you Hypers! We have experienced it in at least two articles: the one about Goedel’s Theorems and the one on Cantor’s Theorem. But we didn’t call it by its name.
I plan to write two articles. In this one, I’ll describe the “original” Diagonal Argument, and in the next one, we’ll talk about the influences and most famous applications of this technique.
Let’s get started!
The Real Problem
As we have learned, Cantor was fascinated with infinite sets and their cardinality (the number of items in them). We now know that not all infinite sets have the same amount of items. Actually, there are infinite ways to be an infinite set!
But in the late 1880’s, Cantor was mostly concerned about two special sets: the set of natural numbers and the set of real numbers. He was wondering if those sets have the same number of items. At this point, maybe you’d bet that they don’t, but the problem is not trivial.
Some years before, Cantor himself proved that there are as many rational numbers as natural numbers. That means that he found a bijection between rationals and natural numbers. We won’t talk about it in this article, but tell me if you are intrigued about this and I’ll include it in a future post.
Note: Note that between any two natural numbers there are infinite rational numbers, and yet, Cantor discovered there are no more rational numbers than natural numbers! This result should be the very definition of mindblowingness.
So, we have as many rationals as natural numbers. Then, adding just the irrational numbers is enough to make the set of real numbers larger than the set of natural numbers?
Now it is not so clear right?..
An Argument Has Born
Forget about real numbers! - said Cantor to himself - we are only considering the [0, 1]
interval. Let’s prove that there are more numbers in this interval than in the entire set of natural numbers.
Let’s suppose a bijection exists between the real numbers in [0, 1]
and the natural numbers. Then, we can arrange them one by one in the following way:
To explain it in a more mathematical way. If f(x) is a bijection from the naturals to [0, 1]
, then we have a correspondence 1 —> f(1), 2 —> f(2), 3 —> f(3), …, n —> f(n), …
That way, in the previous table we have f(1) in the first row, f(2) in the second one, and so on. Note that we don’t care what number f(1) is, we just know it is greater than zero and less than one. The numbers in the previous table are only used as an example.
Now let’s focus on the decimal part of the above numbers (the part that comes after the point). We are about to do something cool! We are going to create a new number that is in the interval [0, 1]
but is not on the table.
We’ll take the first decimal digit of the first number and add it one. That’ll be the first digit of our new number. Then, we’ll do the same with the second digit of the second number to get the second decimal digit of our new number. We repeat this process for all rows of the previous table to create the decimal representation of our new number.
When we encounter a nine, we substitute it with a zero instead of adding one.
We created a number that is not equal to the first number of the list because its first digit does not match the first digit of the first number. For the same reason, this number we created is not equal to the second number of the previous list. Long (infinite) story short, we won’t find any number in the list that is equal to the number we created. We just came up with a new number!
That means that f(x) is not a bijection, because there is no natural number that is in correspondence with our new number. That’s why we conclude that there are more real numbers than natural ones.
In the article when we learned how to count, we said that when we can define a bijection between any subset of the natural numbers and the items of some other set, we say that the other set is countable.
That means that I can arrange the elements of that set in a list like the previous one and all the elements will be in the list. The set of real numbers is an uncountable set and, as we just discovered, it is impossible to arrange them in such a list.
Conclusion
It is easy to see why this technique is known as the Diagonalization technique or the Cantor’s Diagonal technique. But this Diagonal Argument is more than this graphical way of finding new numbers.
We can apply this exact same technique to prove that the set of the infinite sequences of zeros and ones is also uncountable, for example. But there is something more general and powerful about this technique.
Diagonalization is not just yet another proof by contradiction. It is about taking a premise and building something absurd from it. It is a blending between constructive techniques and reductio ad absurdum, two techniques that are often seen as very separated from each other in Math demonstrations.
But this is a topic for an upcoming Tuesday. I promised this one would be short :)
Thank you very much for reading Under the Hype. If you liked it, let me know by hitting that heart. Don’t hesitate to reply with any doubts, suggestions, or corrections.
See you next Tuesday!