An Argument to Rule them All
In this last post about Georg Cantor and his Diagonal Argument, we'll discuss the influence of this technique in the history of Math and Computer Science. We also talk about Legos.
Hello, Hypers!
It seems that I’m a big fan of writing series. I started to write about Combinatorics and it all got me into Georg Cantor and Cantor’s Diagonalization. Today (several weeks after), I’m closing this topic for now.
I think I reserved the best for the end. What I love about the Diagonal Argument is not just its intrinsic beauty, but how it has influenced the course of Math and Computer Science. Cantor not only gave us amazing results, but he also gave us a technique to find even more awesome facts. He gave us both the fish and the rod.
Let’s get started!
Forget About The Diagonal
In a previous post, we saw how Cantor proved there are more real numbers than natural numbers. This very graphic demonstration gave its name to the Diagonal Argument.
This specific example of an application of the argument could work for some other cases. For example, we can demonstrate that the set of all infinite sequences of zeros and ones is not countable either. But it is hard to see how this diagonal construction can help us in other areas like Computer Science.
The name of the Argument itself hides its tremendous power. We need to get rid of this diagonal image to be able to appreciate the full potential of Cantor’s technique.
That’s why I propose to change the name of Cantor’s Diagonal Argument to another that better represents its essence. I propose The Dark Lego Builder.
The Dark Lego Builder
Everybody loves Legos. That’s a fact. Entering a Lego store is an amazing experience. They have a lot of Lego sets to build really cool stuff. But, unfortunately, there is a villain in the Lego world.
His name is Groeg. He can take any set of Lego pieces and build something dark. For example, he took a Lego set that was intended to build a Christmas scene and turned it into a Halloween scene. A total disaster.
However, maybe Groeg is not exactly a villain. He just has a talent. He is here to prove that no matter the colors and intentions Lego Masters put in when creating a Lego set, it is always possible to find a way to build something less cheerful. We can say that there is nothing wrong with Groeg, it is just a problem with the intrinsic nature of Legos.
Although Groeg is a fictional character I just came up with, it has shown us a much better image of the Diagonal Argument. This technique is not about looking for diagonals. It is about building something impossible, or at least surprising while following the rules of a specific system. Like Groeg, who always finds a way to build dark scenes from any Lego set.
How and Where is the Diagonal?
Now that we have a better image of the Diagonal Argument we can start talking about its power and influence. Let’s start by giving a more precise and general description of how the argument is applied.
We always start with a Lego set… I mean, with a system with its own rules. For example, when Cantor tried to prove there are more real numbers than natural ones, he relied on Number Theory and the Real Numbers System.
The goal then is to build the dark scene from those rules and systems. When we say “dark scene“ we are not necessarily referring to something impossible or contradictory as we’ll see later.
In the case of Cantor's proof, he included the premise that a bijection between reals and naturals exists. From that assumption and the existing rules, he was able to build a new real number that was not included in the bijection. This new number was his dark scene. This proved that the premise he initially assumed was false.
But this is not the first example of a Diagonal Argument we have seen in this newsletter. Previously, we had seen the Cantor’s Theorem. It says a power set always has more items than the original set. In this case, Cantor also assumed a bijection between both sets existed and found an impossible subset. This subset was the dark scene.
But these usages are just the tip of the iceberg.
Gödel’s Diagonal
Even before talking about Cantor, we published a post about Gödel’s Theorems. But these theorems came some decades after Cantor’s results. Even more, they are a beautiful example of how to use the Diagonal Argument.
This time Gödel didn’t build an impossible or contradictory dark scene. He built a proposition that said: “I am not provable in this theory“. This was the dark scene. Gödel proved that this proposition can be built with any theory that includes some part of Number Theory.
As we saw in that post, the demonstration of Gödel’s theorems is almost all about building this tricky proposition. For me, this captures the essence of the Diagonal Argument as much as the original Cantor’s Proof does.
Turing’s Diagonal
Although we haven’t talked about it, you probably know what the Halting Problem is. It is about whether it’s possible to build an algorithm that tells if another algorithm will run forever. We won’t dedicate time to talk about this problem now (but tell me if you’d like to see a post about it here in Under the Hype).
(Spoiler alert) To prove that such an algorithm cannot exist, Turing created an impossible algorithm. An algorithm that runs forever only when it doesn’t run forever. This impossible algorithm is the dark scene of this proof.
Conclusions
We could make the post a lot longer. For example, we can talk about Ackerman’s Diagonal (another good topic for a post!). But I think you get the idea. The Diagonal Argument is not just a Diagonal but a much more general way of proving things.
Although this technique is often used in a reductio ad absurdum context. Cantor’s Diagonal is not a proof-by-contradiction technique per se. For example, Gödel used it in a constructivist way.
Actually, Cantor’s Diagonal is a constructive technique. If you build your dark scene on top of false hypotheses, then you should get an impossible construction. But if you build the scene on top of “good foundations“, you’ll get a true proposition, although it might seem incredible sometimes.
In this post, I don’t want to just enumerate infamous usages of the Diagonal Argument. My deeper intention is to show you how influential the work of Georg Cantor was. He gave future geniuses the tools to face problems as challenging as the ones he faced. His legacy is, without any doubt, fundamental in the history of Math and Computer Science.
And that’s it! I hope you have enjoyed this article and all the previous ones about Cantor and the Diagonal Argument. If you think I missed something, please let me know. Thank you very much for reading and supporting me each week.
See you next Tuesday!