Skip to main content
\(\require{cancel} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section5Romantic 8

The first half of the 19th century is viewed as the Romantic Age in European music, art, and literature. Artists turned away from the rationalism of the previous age, and began drawing inspiration from emotional responses to the natural world and the world of ideas, including the concept of infinity. Edmond Burke once wrote[2]: “Infinity has a tendency to fill the mind with that sort of delightful horror, which is the most genuine effect and truest test of the sublime.”

Meanwhile, mathematicians turned their attentions to placing much of the mathematical achievements of the previous centuries on rigorous footing. Set theory plays an important role in this foundation, and one of the pioneers of this field was Georg Cantor. Born in St. Petersburg in 1845, Cantor was a highly original mathematician who studied, among other things, the sizes of sets. \(8\) found a kindred spirit in Cantor. Together they looked at infinity and, to everyone's delightful horror, they proved that it comes in different sizes.

In general, how do we tell whether two sets are the same size? Perhaps we can count the number of elements in each one and compare the numbers. But what if we can't count them all? We could try pairing the elements of one set with the elements of the other to see whether any are left over. For instance, I know the set of vowels \(\{A, E, I, O, U, Y\}\) and the set of days \(\{\) Monday, ... , Sunday\(\}\) are different sizes because I cannot pair their elements exactly. Here's the transcript of one of my early attempts at a pairing:

MPH: Ok, let's see... \(A\) stand over there with Tuesday. Thank you!
Now, \(E\text{,}\) next to Thursday, please. \(I\text{,}\) with Monday...
\(Y\text{:}\) How about \(O\) with Saturday?
MPH: Fine by me... thanks. Ok... now, how about \(U\) with Friday.
\(Y\text{:}\) Great!
MPH: \(Y\text{,}\) I was pointing at \(U\text{.}\) I want \(U\) with Friday.
\(Y\text{:}\) Right, and now I'm standing next to him.
MPH: No, not you, \(Y\text{.}\) You, \(U\text{.}\)
\(Y\text{:}\) Ohhhhh!
\(O\text{:}\) What?
Saturday: \(O\) is with me.
MPH: Yes, that's what I said.
\(I\text{:}\) I didn't say anything.
\(Y\text{:}\) \(I\text{,}\) must you refer to yourself in the third person?
\(I\text{:}\) Huh?
MPH: Ok, I want \(U\) with Friday. \(Y\) stand with Sunday.
Sunday: Why not? I'm a friendly day. What did I do?
\(I\text{:}\) I didn't do anything!
\(Y\text{:}\) There goes \(I\) all third person again...
MPH: Quiet, please! Anyone leftover? Dang! Wednesday.
Okay, let's try this one more time...

No matter how things get paired, one day will be left out. The set of days is larger than the set of vowels. I have also learned that it is easier to attempt a pairing by making a chart or table. The attempt recorded above can be summarized in this way:

vowel A E I O U Y
day Tue Thu Mon Sat Fri Sun

With this view of comparing sizes, we may turn to infinite sets. For instance, we may compare the set of natural numbers \(\mathbb{N} = \{ 1, 2, 3, \ldots\}\) with the set of integers \(\mathbb{Z} = \{\ldots -3, -2, -1, 0, 1, 2, 3, \ldots\}\text{.}\) Now, \(\mathbb{Z}\) may appear to be much larger because everything that is in \(\mathbb{N}\) is also in \(\mathbb{Z}\text{,}\) and still \(\mathbb{Z}\) contains other numbers such as 0 and all the negative integers! In fact, the sets have the same size because we can pair the elements of \(\mathbb{N}\) precisely with the elements of \(\mathbb{Z}\) so that neither set has any elements left over. The table below suggests how to do this:

\(\mathbb{N}\) 1 2 3 4 5 6 7 ...
\(\mathbb{Z}\) 0 1 -1 2 -2 3 -3 ...

Convinced? If not, maybe this will help. We can describe the pairing by this rule: If the natural number \(n\) is even, it gets paired with the integer \(n/2\text{,}\) and if \(n\) is odd it gets paired with the integer \((1-n)/2\text{.}\) Using these rules one can check that each element of \(\mathbb{N}\) gets paired with one element of \(\mathbb{Z}\) and each element of \(\mathbb{Z}\) gets paired with one element of \(\mathbb{N}\text{.}\) So \(\mathbb{N}\) and \(\mathbb{Z}\) are the same size. Intuition that we have developed about the sizes of finite sets just doesn't apply to infinite sets.

Here's an even more astonishing example. A little known French mathematician named Michel Vivelatrois, a product of this author's artistic license, built an infinite two-dimensional array of 3s as suggested below.

1 2 3 ...
1 3 3 3 ...
2 3 3 3 ...
3 3 3 3 ...
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)

The array has one row for each natural number and one column for each natural number, and every entry in the array is 3. (If I may be frank, Vivelatrois exhibited an unhealthy number obsession.) To his dismay, Vivelatrois discovered that the total number of 3s in this array is no larger than the set \(\mathbb{N}\text{.}\) Can you find a way to pair up each 3 in this array with its own natural number? There is a way!

In light of such examples, numbers began gathering in coffee houses around central Europe to listen to Chopin Mazurkas and to try assembling themselves into sets larger than \(\mathbb{N}\text{.}\) Alas, they all suffered the fate of Vivelatrois' array of 3s.

Enter Cantor and \(8\text{.}\) Suppose we build a sequence consisting of just \(8\)s and \(G\)s, such as this one:

\begin{equation*} 8, 8, G, 8, G, G, 8, \ldots \end{equation*}

There is no rhyme or reason to this sequence. We just require that each term is an \(8\) or a \(G\text{,}\) and that the sequence does not terminate. Two such “Great \(8\)” sequences are different as long as they disagree in at least one spot. Now, let \(\mathbb{S}\) denote the set of all possible Great \(8\) sequences. Cantor proved that the set \(\mathbb{S}\) is larger than \(\mathbb{N}\) using a technique that is now called Cantor's diagonalization argument. Here's how it works.

Assume initially that \(\mathbb{S}\) and \(\mathbb{N}\) have the same size. This means the elements of the two sets can be precisely paired with one another. Suppose such a pairing is given in the form of a table, as suggested below (ignore the highlighted values for now).

\(\mathbb{N}\) \(\mathbb{S}\)
1 8, 8, 8, 8, 8, \(\ldots\)
2 8, 8, G, 8, G,\(\ldots\)
3 G, 8, G, 8, G,\(\ldots\)
4 8, 8, G, G, G, \(\ldots\)
5 8, G, G, G, 8, \(\ldots\)
\(\vdots\) \(\vdots\)

Cantor argued that this couldn't possibly be a complete pairing of the two sets by demonstrating that there must be some element in \(\mathbb{S}\) that is not in this list. We construct a Great \(8\) sequence, let's call it \(x\text{,}\) by first considering the “diagonal” entries in this listing, as highlighted. These diagonal entries themselves determine a Great \(8\) sequence (which begins \(8\text{,}\) \(8\text{,}\) G, G, \(8, \ldots\)).

We then form the sequence \(x\) by assigning at each position the opposite value to the one at the corresponding position of the diagonal sequence. Thus, the sequence \(x\) begins G, G, \(8\text{,}\) \(8\text{,}\) G, ... . This Great \(8\) sequence will be different from every sequence in the list. Indeed, \(x\) is different than the first sequence in the list because their first entries will be different, and \(x\) is different from the second sequence in the list because their second entries differ. In particular, \(x\) will differ from the \(n\)th sequence in the list because their \(n\)th terms will differ. We are forced to conclude that no pairing of \(\mathbb{N}\) and \(\mathbb{S}\) is possible.

What this means, as Cantor realized, is that while both sets are infinite, the set \(\mathbb{S}\) is larger. Thus did \(8\) and Cantor introduce us to different sizes of infinity, prompting David Hilbert to write in his 1926 paper Uber das Unendliche [3], “Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben konnen.” My translation reads: “No one shall expel us from the paradise that Cantor and \(8\) have created.”