# Hypergame and Cantor’s Theorem, Part I

Note: I have added a page, Sets, Functions, and Cardinality, which introduces basic mathematical notions and notations that will be useful for us. Those of you with some mathematical background can safely skip it, possibly referring back to it if something unfamiliar arises. Others may find it helpful to read that page before reading this and future mathematical posts. I will assume in this post that the reader is familiar with the notions of power set and cardinality, which are covered in the linked page. If anything remains unclear, please let me know!

Set theory, and with it the modern mathematical study of infinity, was arguably born in 1874, when Georg Cantor first published his now-celebrated result that the set of all real numbers is strictly larger than the set of all natural numbers. This was the first demonstration that there are multiple sizes of infinity and opened the door to a vast realm of mathematical investigation. In 1891, he published a second proof, introducing what came to be known as the diagonal argument, a beautiful and versatile tool. (First exposure to the diagonal argument is a pivotal moment in the lives of many young mathematicians. I first came across it in high school, in The Man Who Loved Only Numbers, Paul Hoffman’s wonderful book about the Hungarian mathematician Paul Erdős.) In fact, in the 1891 paper, he proved a more general theorem, known today as Cantor’s Theorem.

Cantor’s Theorem: For every set $X$, the power set of $X$ is strictly larger than $X$, i.e. $|X| < |\mathcal{P}(X)|$.

(To see that this theorem does indeed generalize the result that $|\mathbb{N}| < |\mathbb{R}|$, it suffices to show that $|\mathcal{P}(\mathbb{N})| \leq |\mathbb{R}|$ (in fact, these two sets have the same cardinality). To show this, we will define a one-to-one function $f:\mathcal{P}(\mathbb{N}) \rightarrow \mathbb{R}$. One way to define such a function is as follows. If $X \in \mathcal{P}(\mathbb{N})$, then let $f(X) = 0.a_0a_1a_2\ldots$, where, for every natural number $n$, $a_n = 1$ if $n \in X$ and $a_n = 0$ if $n \not\in X$. I will leave it to the reader to check that this does in fact define a one-to-one function from $\mathcal{P}(\mathbb{N})$ into $\mathbb{R}$.)

By iterating the power set operation, Cantor’s Theorem shows us that the world of infinity is exceedingly rich; there is in fact an infinity of different infinities. For example:

$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < |\mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N})))| \ldots.$

(I am in fact understating my case here. Not wanting to become too technical, let me just mysteriously and somewhat vaguely say that the number of infinities is itself larger than any set.)

Cantor’s Theorem was immediately polarizing in the mathematical world. Some influential mathematicians were strong supporters of Cantor’s work who recognized and appreciated the possibilities it opened up. This group included David Hilbert, who famously proclaimed:

No one shall expel us from the paradise that Cantor has created for us.

Many other mathematicians, though, were resistant. Before Cantor, mathematics had dealt with infinity primarily as a potential infinity, an infinity that can be approached but never attained, and had shied away (with some notable exceptions, such as Leibniz and possibly Archimedes) from the notion of an actual infinity, or a completed infinite totality. Many thus objected to what they saw as Cantor’s cavalier application of mathematical and logical methods to infinite sets such as $\mathbb{N}$ and $\mathbb{R}$. Leopold Kronecker, a great mathematician and arguably Cantor’s arch-nemesis, put his distaste particularly harshly:

I don’t know what predominates in Cantor’s theory – philosophy or theology, but I am sure that there is no mathematics there.

Cantor’s ideas gradually came to to be accepted by the mathematical establishment, but the uneasy feeling that set theory is more theology than mathematics lingered among mathematicians of a certain philosophical disposition. Hermann Weyl, a prominent mathematician, physicist, and philosopher, wrote the following about Cantor’s work and subsequent developments in set theory in his 1946 paper, “Mathematics and Logic.”

But in the resulting system mathematics is no longer founded on logic, but on a sort of logician’s paradise, a universe endowed with an “ultimate furniture” of rather complex structure and governed by quite a number of sweeping axioms of closure. The motives are clear, but belief in this transcendental world taxes the strength of our faith hardly less than the doctrines of the early Fathers of the Church or of the scholastic philosophers of the Middle Ages.

(I think “ultimate furniture” is one of my new favorite expressions.)

Cantor’s diagonal argument is already covered wonderfully in many other places. I can recommend the following TED-Ed video by Dennis Wildfogel:

Here, though, I want to present a slightly different proof, due to William Zwicker, of Cantor’s Theorem. The proof uses ideas from the analysis of Hypergame, a delightful pseudo-paradoxical thought experiment. Come back on Thursday to find out more.