The price of facing Infinity
This is the history of how a man defeated infinity and how much he had to pay for it.
Hello, Hypers!
The history we are going to talk about is both sad and fascinating. We are going to know how a man defied infinity. While the results he achieved were outstanding, the incomprehension of his contemporaries caused our protagonist to suffer from chronic depression, ultimately leading him to his death.
We are going to talk about Georg Cantor and the Cantor’s Theorem.
A little bit of history
Let’s start by giving some historical context. Cantor was born in Saint Petersburg, in the czarist Russia, in 1845. However, his family moved to Germany when he was young. It seems he had a talent for playing the violin, but Mathematics soon became his passion.
He studied at the University of Berlin, which was the center of the German Mathematical movement at that time. Leopold Kronecker, Karl Weierstrass, and Ernst Kummer were among his teachers. If you have studied some calculus and algebra, these names should be familiar to you. Cantor got his doctoral degree in 1866.
We are not going to make a review of all of Cantor’s results and publications. In this post, I would like to focus on the idea that could be the summary of his entire career:
He discovered that two infinite sets can have different sizes
In other words, this means that there are different kinds of infinities. Actually, as we’ll see very soon, there are infinite kinds of infinities. Don’t believe me?
Measuring the Infinity
For centuries, the usual consensus about infinity was that there exists only one kind of it. Infinite sets were considered all to be equally infinite. This is what common sense tells us. I thought this way not so many years ago. It even had an important theological significance. The unicity and immensity of the infinite were related to God.
One can guess now that the work of Cantor was not exactly popular. But let’s talk about it later. How he was able to deal with infinities? One of the fundamental tools to face this challenge was his trick of comparing infinities.
Remember how two weeks ago we talked about clever ways to count? If you don’t, this is a perfect moment to refresh it. I’ll be waiting for you. Ready? Well, the idea of using bijective relationships to count was invented by Georg Cantor. We saw how this trick can be leveraged to find the size of some finite sets, but it is when dealing with infinite sets that the power of this idea is really unleashed.
Actually, this trick is the only way we can face infinite sets. This is one of the reasons why nobody questioned infinities before. Because Cantor was the father of the method to make this questioning.
Although we are only using the bijection idea in this article, I think it is important to mention that Cantor not only defined the equality of set sizes with bijections. He also defined order relations between different set sizes using other kinds of relationships. This is why Cantor is considered today as the father of modern Set Theory. A foundational Theory from which all the math is derived. If Alan Turing is, without any doubt, the father of Computer Science, I would say that Georg Cantor is one of its grand-grandfathers.
Cantor’s Theorem
This Theorem was published by Cantor in 1891. His discoveries involving infinite sets were widely known at this time. He had recently gone through a period away from Mathematics due to his first depressive attack. This attack was caused by the rejection of many important Mathematicians and Philosophers like his former teacher Kronecker and Ludwig Wittgenstein.
Back to the Theorem, let’s define one important concept:
Given a set A, the power set of A denoted by P(A) is the set of all the subsets of A.
For example, the power set of the set {1, 2, 3} is {{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}}. Note that the empty set ({}) and the entire set {1, 2, 3} are part of the power set.
Now we can formulate the Cantor’s Theorem:
Given a set A, the power set of A has more items than A itself.
Of course, the exact formulation is a little bit trickier but, in essence, it is equivalent. We are using this one to save time by not having to learn more notation.
It feels quite trivial right?
The Proof
In the example we saw earlier for {1, 2, 3}, the power set had many more elements. It is easy to prove that, for finite sets, the power set has always more elements than the original one. Even further, given the number of items in a finite set, we can know immediately how many items are in its power set. But this is left to the reader as an exercise (like if this was a fancy Math book).
However, let’s note that the Theorem doesn’t specify whether the set A is finite or infinite. How can we prove this relation between a set and its power set for infinite sets?
It is easy to realize that the power set of an infinite set is also an infinite set. How an infinite set can have more items than another infinite set? This got hairy too quickly!
The first thing to note is that for each element x in A, there is an element {x} in P(A). So we can safely say that the number of items in P(A) cannot be less than the number of items in A. Now we need to prove that these numbers cannot be equal. Then, the only possible conclusion would be that P(A) has more items than A, even when both are infinite sets.
As we learned before, we’ll say two sets have the same number of items if we can define a bijection between the items of both sets. Then, we need to demonstrate that it is not possible to find such a bijection between A and P(A). This still seems too complicated to do considering infinite sets.
It is very complicated indeed. We are going to prove it by assuming the opposite and getting a contradiction, which will mean that our premise (i.e. a bijection exists) is false.
Let’s say f: A → P(A) is a bijection between A and P(A). Now let’s build the following set B = { x in A, such that x is not in f(x)}. Note that B is a subset of A, then B is in P(A). To understand better the definition of B, note that f(x) is a subset of A. If x is not in f(x) then it is in B, otherwise, it is not part of B.
As f is a bijection, there exists an element y in A, such that f(y) = B. However, by definition, y is in B if, and only if, y is not in f(y). But f(y) = B, so the previous proposition is equivalent to: y is in B if, and only if, y is not in B. And, of course, this is a contradiction. We can conclude that it is not possible to define a bijection f between A and P(A).
As A and P(A) cannot have the same number of items and P(A) has at least as many items as A, we can conclude that P(A) has always more items than A. This holds even for infinite sets.
Conclusions
Cantor’s Theorem is quite fascinating by itself (at least for me), but it has one further implication: there are infinite kinds of infinities.
Given any set, we can define the power set of that set, and we’ll have a bigger set. For A we can define P(A), but then we can define P(P(A)). That is, the power set of the power set of A. If A is an infinite set, then all the subsequent power sets are more infinite than the previous ones.
We’ll write an entire post about the demonstration technique we just used to prove Cantor’s Theorem. This was also an amazing breakthrough by Cantor and since then, has been behind many of the most mind-blowing results in Math and Computer Science. That’s another reason to say that Cantor is one of the grand-grandfathers of Computer Science.
Unfortunately, Cantor was always criticized for his results. He never found the recognition he deserved. This constant rejection from many of his contemporaries caused his first depressive crisis during his youth.
He stayed away from the Mathematic academic world for more than ten years. During that time, he studied and lectured about philosophy and Shakespearean literature. He had his own theory about the Shakespearean Authorship Question.
He got back to publishing and researching in the late 1800’s and the beginning of the 1900’s. During this decades, he formulated the theorem we just studied. He also discovered that there are more real numbers than natural numbers. These breakthroughs would be incredibly influential in the upcoming decades. But at that time, Cantor’s ideas faced new resistance and critiques.
He thought God had chosen him to communicate these astonishing ideas about infinities. After a life full of rejections, he convinced himself that God had abandoned him.
After many years of suffering chronic depression, Georg Cantor died in a sanatorium in 1918. For me, it is impossible to avoid thinking about the similarly unfortunate deaths of other subsequent geniuses like Goedel and Turing. Maybe Cantor just paid the price of facing the infinity.
Thanks for another week of reading Under the Hype. I hope you have enjoyed this post. Please, tell me if you would like more theoretical posts like this one for the upcoming weeks.
See you next Tuesday!
Good point about geniuses suffering similar fates. In order to stretch the boundaries of the known, such pioneers often rub up against incredible resistance. We're not really wired for rapid change, so when a new idea like this upturns the status quo, the status quo really digs in and pushes back.
The results are often tragic.
Fortunately, infinities are really fun to think about!