Part VIII · Foundations Chapter 52 of 60

Infinities

Galileo’s three characters argue about which is larger: the natural numbers or the points of a segment. On the way they meet a hotel that always has a free room, Cantor’s diagonal and a tower of infinities with no top floor.

Years 1–2 55 minutes

Builds on: 51 · Logic and sets

You will learn

prove that a set is countable and build an explicit numbering
explain Cantor’s diagonal argument and why a segment has more points than there are natural numbers
compare cardinalities of sets with the Cantor–Bernstein theorem
understand why there’s no largest infinity and what the independence of the continuum hypothesis means

4Are there more whole numbers or points on a line segment?

Line VIII · Foundations

You are here: 52 · Infinities

Interchanges 6 · Root two

The last chapter ended with an oddity. The shift $n \mapsto n + 1$ fits all the natural numbers into their own part $\{2, 3, 4, \dots\}$ without losing or merging a single one. That can’t happen with finite sets: there an injection into a set of the same size has to be a bijection. Can infinities be compared at all, then? That’s the fourth big question of the course: which is larger, the natural numbers or the points of a segment?

The first to ask it seriously was Galileo Galilei. In 1638 his last book, Discourses and Mathematical Demonstrations Relating to Two New Sciences, came out in Leiden. Galileo wrote it under house arrest at Arcetri and, like his earlier Dialogue Concerning the Two Chief World Systems, built it as a conversation between three friends. Salviati speaks for the author, Sagredo is a clever and enthusiastic listener, and Simplicio defends Aristotle and common sense. They discuss the strength of beams and the fall of bodies, but on the first day Salviati is distracted by a puzzle about numbers. Let’s let them finish their conversation. One liberty: suppose Salviati has on his desk the works of Georg Cantor, written two hundred and fifty years later. The beginning of the conversation follows Galileo closely, the rest is invented, but the mathematics in it is real.

Day one. Squares and roots

Salviati. We call the numbers $1, 4, 9, 16, \dots$ squares: the products of a number by itself. All other numbers aren’t squares. Which are more numerous: all the numbers together, or the squares alone?

Simplicio. All the numbers, of course. The squares are only part of the numbers, and the whole is greater than the part. Euclid said so long ago.

Salviati. And the further you go, the rarer the squares. Among the first hundred numbers there are ten, among the first ten thousand a hundred, among the first million a thousand: the share falls from a tenth to a thousandth. But let me ask differently: how many squares are there in the world? Each square has its root, each root its square, and no square has two roots. So there are as many squares as roots. And the roots are all the numbers.

Sagredo. So the squares are both fewer than all the numbers and just as many. What should we conclude from that?

So far as I see we can only infer that the totality of all numbers is infinite, that the number of squares is infinite, and that the number of their roots is infinite; neither is the number of squares less than the totality of all numbers, nor the latter greater than the former; and finally the attributes “equal”, “greater” and “less” are not applicable to infinite, but only to finite, quantities.

Galileo Galilei, Two New Sciences, First Day, 1638. Translation after H. Crew and A. de Salvio

Salviati. That’s what I thought then. But Cantor, whose papers I’m now looking through, did the opposite: instead of forbidding the comparison, he took its definition seriously. Think of a shepherd who can’t count. In the morning he puts a pebble in his bag for each sheep he lets out, and in the evening he takes out a pebble for each sheep that returns. If the pebbles and the sheep run out together, there are as many of one as of the other, and no numbers were needed.

Sagredo. Pairs instead of counting. And that works for infinite flocks too.

Sets $A$ and $B$ are called equinumerous, written $|A| = |B|$, if there’s a bijection between them. What all mutually equinumerous sets have in common is called their cardinality. For a finite set the cardinality is simply the number of elements.

The set of squares $\{1, 4, 9, 16, \dots\}$ is equinumerous with the set $\mathbb N$ of all natural numbers.

We have to exhibit a bijection. Salviati himself proposed it: each number goes to its square.

Assign to each natural $n$ the square $n^2$. The arrows go from the top row, $\mathbb N$, down to the squares on the number line.

Different numbers go to different squares: if $m < n$, then $m^2 < n^2$. So the map is an injection.

An arrow leads into every square: a square $k$ by definition equals $n^2$ for some natural $n$, and there’s an arrow from $n$ into it. So the map is a surjection.

The map $n \mapsto n^2$ is a bijection between $\mathbb N$ and the set of squares, and they’re equinumerous. The squares thin out as they go: up to $N$ there are about $\sqrt N$ of them. But for cardinality all that matters is that there are enough pairs for everyone.

Simplicio. But then the part equals the whole! That’s absurd.

Salviati. Absurd for finite sets: there it’s a theorem from the last chapter. For infinite ones it’s their distinguishing mark. Richard Dedekind defined it exactly so in 1888: a set is infinite if it’s equinumerous with some part of itself other than itself. Euclid’s axiom about the whole and the part is true for segments and figures, but it can’t be applied to sets of points.

If “having as many elements” is a sensible notion, it should behave like equality. And so it does.

Equinumerosity is reflexive, symmetric and transitive, that is, it’s an equivalence relation.

The idea: the identity map, the inverse of a bijection and the composition of bijections are again bijections.

Reflexivity: the map $a \mapsto a$ is a bijection of $A$ onto itself. Symmetry: if $f\colon A \to B$ is a bijection, it has an inverse $f^{-1}\colon B \to A$, and that’s a bijection too, because its inverse is $f$ (the theorem on invertibility). Transitivity: let $f\colon A \to B$ and $g\colon B \to C$ be bijections. The composition $g \circ f$ is injective: from $g(f(a)) = g(f(a'))$ the injectivity of $g$ gives $f(a) = f(a')$, and hence $a = a'$. And it’s surjective: for $c \in C$ there’s a $b$ with $g(b) = c$, and for this $b$ an $a$ with $f(a) = b$; then $g(f(a)) = c$.

Day two. The hotel that always has room

Sagredo. I’ve heard that David Hilbert, in a lecture in 1924, told of a hotel with infinitely many rooms $1, 2, 3, \dots$ They’re all occupied, and a new guest arrives.

Simplicio. No vacancies. Everything’s taken means everything’s taken.

Salviati. But the receptionist asks each guest to move from room $n$ to room $n + 1$. Nobody is left without a room, nobody shares with a neighbour, and room one is free.

The hotel’s floors have ten rooms each. Take in a new guest, a bus with infinitely many passengers or an infinite column of buses, and follow where each guest moves. Guests above the fifth floor aren’t shown, but the moving rule works for them too.

Sagredo. And if a bus pulls up with as many passengers as there are rooms?

Salviati. Then the guest from room $n$ moves to room $2n$, and all the odd rooms become free. The passenger in seat $k$ gets room $2k - 1$. And for an infinite column of buses, a formula we’re about to derive will help. The hotel story, by the way, was made famous not by Hilbert but by the physicist George Gamow: he retold it in his book One Two Three… Infinity (1947).

A set is called countable if it’s equinumerous with $\mathbb N$: its elements can be written as a sequence $a_1, a_2, a_3, \dots$ in which each one appears exactly once. In 1895 Cantor denoted the cardinality of a countable set by $\aleph_0$, “aleph-null”, after the first letter of the Hebrew alphabet. An infinite set that isn’t countable is called uncountable.

The even numbers, the squares, the powers of two are countable sets: the numbering is ready-made. So are the integers, though they’re infinite in both directions: the list $0, 1, -1, 2, -2, 3, -3, \dots$ misses nobody, and a number $k > 0$ stands in it at place $2k$, and $-k$ at place $2k + 1$. A hotel already occupied by all the natural numbers can take in pairs too. That’s the main tool of the day.

The pairs $(p, q)$ of natural numbers are laid out in a table and walked through along diagonals on which the sum $p + q$ is constant. The diagonal with sum $s$ holds $s - 1$ pairs, and all the earlier ones together $1 + 2 + \dots + (s - 2) = \frac{(s - 1)(s - 2)}{2}$ pairs (Gauss’s formula).

The pair’s place on its diagonal: we walk the diagonal from $(1, s - 1)$ to $(s - 1, 1)$, so the pair with first number $p$ is $p$th on it.

Example: $c(3, 2) = \frac{4 \cdot 3}{2} + 3 = 9$. Indeed, the pairs go like this: $(1, 1)$, $(1, 2)$, $(2, 1)$, $(1, 3)$, $(2, 2)$, $(3, 1)$, $(1, 4)$, $(2, 3)$, $(3, 2)$, the ninth.

The set $\mathbb N \times \mathbb N$ of all pairs of natural numbers is countable.

The trick is to walk through the table not by rows (the first row never ends) but along short diagonals.

Lay out the pairs in an infinite table: column $p$, row $q$ holds the pair $(p, q)$. Each pair occupies exactly one cell.

Diagonal number $s$ is the cells where $p + q = s$. It has exactly $s - 1$ cells, and each pair lies on exactly one diagonal.

Number the diagonals in turn, $s = 2, 3, 4, \dots$, and within a diagonal by increasing $p$. Each diagonal is finite, so the walk reaches any of them in finitely many steps.

The number of a pair is computed by the formula $c(p, q)$: first all the pairs with smaller sums, then the place on its own diagonal. Different pairs get different numbers, and each number $1, 2, 3, \dots$ goes to some pair.

So $c$ is a bijection $\mathbb N \times \mathbb N \to \mathbb N$, and the set of pairs is countable. An infinite column of buses is accommodated like this: the passenger in seat $k$ of bus $b$ gets room $c(b, k)$, and the hotel’s residents count as the passengers of bus number $1$.

What number does the pair $(2, 5)$ get when walking along the diagonals?

$p + q = 7$, the earlier diagonals hold $1 + 2 + 3 + 4 + 5 = 15$ pairs, and on its own diagonal the pair $(2, 5)$ is second. The number is $15 + 2 = 17$. By the formula: $c(2, 5) = \frac{6 \cdot 5}{2} + 2 = 17$.

We’ll need a simple but useful lemma next.

Every infinite subset of a countable set is countable.

The idea: go through the list of the original set and renumber only the elements that lie in the subset.

Let $A = \{a_1, a_2, a_3, \dots\}$ be a countable set, and $B \subset A$ infinite. Go through the list $a_1, a_2, \dots$ and write down in turn the elements that belong to $B$: the first one met gets number $1$, the next number $2$, and so on. Every element of $B$ stands at some finite place in the list of $A$, so it gets a number. Different elements get different numbers. And the numbers never run out, because $B$ is infinite. This is a bijection between $\mathbb N$ and $B$.

The set $\mathbb Q$ of rational numbers is countable.

The idea: a fraction is a pair of numbers, and the set of pairs is countable.

Each positive rational number is written uniquely as a fraction in lowest terms $\frac pq$ (chapter 5). Assign to it the pair $(p, q)$. Different numbers get different pairs, so the positive rationals are equinumerous with an infinite subset of $\mathbb N \times \mathbb N$, the one where $p$ and $q$ are coprime. By the lemma it’s countable: $r_1, r_2, r_3, \dots$ Write the whole of $\mathbb Q$ as the list $0, r_1, -r_1, r_2, -r_2, \dots$, as we did with the integers.

The fractions $\frac pq$ are laid out in a table and walked through along diagonals; reducible ones, like $\frac24$, are skipped, because that number already has a place. Tap any cell or type a fraction to find its place in the list.

This list isn’t the only one. In the chapter on fractions the Stern–Brocot tree contained each positive fraction exactly once, and it’s enough to read it level by level, left to right: the levels are finite, and every fraction’s turn will come.

Sagredo. The fractions stand on the line so densely that between any two there’s a third, and yet they can be numbered. And the roots of equations?

Salviati. Those too. It’s the first thing Cantor proved about infinities, in a paper of 1874.

The set of all algebraic numbers, the roots of polynomials with integer coefficients that aren’t identically zero, is countable.

The idea: assign each polynomial a natural number, its “height”, so that there are finitely many polynomials of each height, and list the roots height by height.

For a polynomial $a_n x^n + \dots + a_1 x + a_0$ of degree $n \ge 1$ with integer coefficients and $a_n \ne 0$, call $h = n + |a_n| + \dots + |a_0|$ its height. There are finitely many polynomials of a given height $h$: the degree is at most $h$, and each coefficient is an integer from $-h$ to $h$. Each of them has at most $n$ roots (chapter 14). First write down the roots of all polynomials of height $2$, then of height $3$, and so on, skipping numbers that have already appeared. At each height finitely many roots are written down, so every algebraic number, being a root of some polynomial of some height, gets a number sooner or later. The result is a list of all algebraic numbers; it’s infinite, because it contains all the integers.

For example, only the polynomials $\pm x$, with root $0$, have height $2$. Height $3$ is had by the polynomials $\pm 2x$, $\pm x \pm 1$ and $\pm x^2$, and they have two new roots: $1$ and $-1$. At height $4$ come $\pm\frac12$ and $\pm 2$, roots of polynomials like $2x - 1$ and $x - 2$, and along with them the imaginary $\pm i$, roots of $x^2 + 1$. The first irrational numbers arrive at height $5$: the polynomial $x^2 - 2$ gives $\pm\sqrt2$, and $x^2 - x - 1$ gives the golden ratio $\frac{1 + \sqrt5}{2}$ and its partner $\frac{1 - \sqrt5}{2}$.

Simplicio. There you are. Numbers, squares, fractions, roots: everything lines up in a single queue. So there’s only one infinity, and Galileo was right: there’s nothing to compare.

Salviati. Come back tomorrow with a list of all the points of a segment.

Day three. The diagonal

Simplicio. I’ve brought it. Each point of the segment is a decimal $0.d_1 d_2 d_3 \dots$, and they’re all in my list.

Salviati. Splendid. Let’s look at the first digit of the first number, the second digit of the second, the third digit of the third: the diagonal. I’ll write a number whose $k$th digit differs from the $k$th digit of the $k$th number of your list. If that digit is a five, I write a four; otherwise I write a five. My number differs from your first number in the first digit, from the second in the second, from each one in at least one digit.

The interval $(0, 1)$ is uncountable: no sequence $x_1, x_2, x_3, \dots$ contains all its points.

We’ll prove something stronger: for any list of numbers from $(0, 1)$ we’ll exhibit a number in $(0, 1)$ that isn’t in the list.

Write each number of the list as an infinite decimal. Some numbers have two expansions, like $0.5 = 0.4999\ldots$; to be definite, take the one that doesn’t end in recurring nines. The number $x_k$ is a row of the table, and its digits are $d_{k1}, d_{k2}, d_{k3}, \dots$

Pick out the diagonal: the first digit of the first row, the second digit of the second, the $k$th digit of the $k$th, $d_{kk}$.

Build a new number $y = 0.e_1 e_2 e_3 \dots$: its $k$th digit is $e_k = 4$ if $d_{kk} = 5$, and $e_k = 5$ otherwise.

The number $y$ differs from every $x_k$. Its digits are only fours and fives, so $y$ has exactly one decimal expansion: two different expansions occur only for numbers one of whose expansions ends in zeros and the other in nines. And the expansion of $y$ differs from that of $x_k$ in the $k$th digit. If $y = x_k$, one number would have two expansions, one of which has no zeros or nines, and that can’t happen.

The number $y$ lies in $(0, 1)$: it’s at least $0.444\ldots$ and at most $0.555\ldots$. And it isn’t in the list. So no list exhausts the interval, and $(0, 1)$ is uncountable.

The most convincing thing about this proof is that it can’t be “patched”. Add the number found to the list, and the diagonal shifts: you get a new number that isn’t in the new list.

Make your own list: a random one, one of famous numbers, or your own by tapping digits. The machine builds, along the diagonal, a number that isn’t in the list. Press “Put y at the top of the list” and watch the list lose again.

Why doesn’t the same diagonal trick prove that the set of rational numbers in $(0, 1)$ is uncountable?

The diagonal builds a number that isn’t in the list, but nothing promises that this number is a fraction. For a list of all the fractions in $(0, 1)$ it’s bound to be irrational, since every fraction is in the list. A contradiction appears only when the list must contain every number of the kind the diagonal produces, for example all the points of the interval.

The interval $(0, 1)$ is only a piece of the line, but it has as many points as the whole line. You can see this in a picture.

The interval $(0, 1)$ is equinumerous with the whole number line $\mathbb R$.

The trick is to bend the interval into a semicircle and project it onto the line from the centre.

Below is the line $\mathbb R$, above it the interval $(0, 1)$ of length $1$.

Bend the interval into a semicircle without its ends, bulging downwards and touching the line at its midpoint. Each point of the interval goes to one point of the arc, and different points to different ones: the bending is a bijection.

From the centre $O$ of the semicircle draw a ray through a point $P$ of the arc. The ray meets the line at exactly one point $X$: it points downwards, and the horizontal rays to the ends of the arc don’t count, since the ends are removed.

Conversely, any point $X$ of the line is joined to $O$ by a segment, and it crosses the arc at exactly one point. So the projection is a bijection of the arc onto the line. The closer $P$ gets to an end of the arc, the further $X$ goes off to infinity.

A composition of two bijections is a bijection, so $|(0, 1)| = |\mathbb R|$. As a formula, the same idea is given by the function $x \mapsto \tan\bigl(\pi(x - \frac12)\bigr)$.

The cardinality of the set $\mathbb R$ of real numbers is called the continuum and written with the Gothic letter $\mathfrak c$. A segment, an interval, the whole line are sets of the cardinality of the continuum.

The segment has more points. The natural numbers form a countable set, of cardinality $\aleph_0$, while the points of a segment form the continuum $\mathfrak c$. Every natural number can be sent to a point of its own on the segment, but no matching covers all the points: Cantor’s diagonal will always find one left over. There are as many fractions, and even algebraic numbers, on a segment as there are natural numbers, but there are more points altogether.

Transcendental numbers exist, and the set of them is uncountable.

The idea: if there were at most countably many transcendental numbers, the whole line would be the union of two countable lists.

Suppose the transcendental real numbers form a finite or countable list $t_1, t_2, \dots$ The real algebraic numbers are an infinite subset of the countable set of algebraic numbers, so by the lemma they’re countable too: $a_1, a_2, \dots$ Every real number is either algebraic or transcendental, so the list $a_1, t_1, a_2, t_2, \dots$ (when the list of $t$’s runs out, carry on with $a$’s alone) contains all the real numbers. This contradicts the uncountability of $\mathbb R$.

Sagredo. What an astonishing way to prove existence! In 1844 Joseph Liouville had to build a transcendental number by hand, and in 1873 Charles Hermite proved the transcendence of $e$ with pages and pages of calculation. And here it’s proved that almost all numbers are transcendental, without naming a single one.

Salviati. As in the story of $\sqrt2^{\sqrt2}$ from the last chapter: knowing there’s treasure isn’t knowing where it’s buried. Though the diagonal, come to think of it, is a perfectly concrete recipe: give it a list of the algebraic numbers, and it will compute, digit by digit, a number that isn’t in it.

Day four. A tower with no top floor

Simplicio. Very well, there are two infinities: the countable and the continuum. The continuum is the last. There can’t be anything more than the points of a line.

Salviati. Take any set $A$ and form the set of all its subsets, $\mathcal P(A)$. For three elements $\{1, 2, 3\}$ there are eight subsets: $\varnothing$, three with one element, three with two elements, and the set itself. For $n$ elements there are $2^n$: each element is either taken or not. For infinite sets too, $\mathcal P(A)$ is always larger than $A$.

The power set $\mathcal P(A)$ consists of all the subsets of $A$, including $\varnothing$ and $A$ itself. Cardinalities are compared like this: $|A| \le |B|$ if there’s an injection $A \to B$, and $|A| < |B|$ if $|A| \le |B|$ but there’s no bijection between $A$ and $B$.

The set of all subsets of $A$.

A strict inequality of cardinalities: $A$ can be embedded in $\mathcal P(A)$ by the injection $a \mapsto \{a\}$, but there’s no bijection between them; no map $A \to \mathcal P(A)$ hits every subset.

Any set at all: finite, countable, the continuum, anything.

Example: for $A = \{1, 2, 3\}$ we get $|\mathcal P(A)| = 2^3 = 8 > 3$. For $A = \mathbb N$ the inequality says that the natural numbers have uncountably many subsets.

For any set $A$ no map $f\colon A \to \mathcal P(A)$ is surjective. So $|\mathcal P(A)| > |A|$.

It’s the diagonal again. Record which elements lie in which subset in a table of ones and zeros, and flip its diagonal.

Let $f$ assign to each $a \in A$ a subset $f(a)$. The row of the table for $a$ marks which elements lie in $f(a)$: a one in column $b$ if $b \in f(a)$.

The diagonal answers the question whether $a$ lies in its own subset $f(a)$.

Form the set $D = \{a \in A \mid a \notin f(a)\}$: the elements that didn’t make it into their own subset. Its row is the diagonal with ones and zeros swapped.

$D$ equals no $f(a)$: the rows of $D$ and $f(a)$ differ in column $a$. If $a \in f(a)$, then $a \notin D$, and if $a \notin f(a)$, then $a \in D$.

So the subset $D$ isn’t hit: $f$ isn’t surjective, whatever $f$ we took. There’s no bijection, but there’s the injection $a \mapsto \{a\}$, so $|\mathcal P(A)| > |A|$. The table in the picture is finite, but the argument never used finiteness.

The set $D$ is a relative of Russell’s set from the last chapter: “those who don’t contain themselves”. Cantor himself noticed in 1899 that his theorem doesn’t allow a “set of all sets” to exist: such a set $V$ would have more subsets than elements, even though each subset is also a set and lies in $V$.

$A$ is a part of the set $B$ other than $B$ itself. What can be said about their cardinalities?

The identity embedding is an injection, so $|A| \le |B|$. A part doesn’t guarantee a strict inequality: the squares are a part of $\mathbb N$, the interval $(0, 1)$ a part of the line, and the cardinalities are equal. Things get strictly bigger when you take all the subsets.

Sagredo. Wait. We found two injections, the part into the whole and the whole into the part, as with the interval and the line. Does it always follow that the cardinalities are equal? For numbers, $a \le b$ and $b \le a$ give $a = b$, but here a bijection still has to be built.

Salviati. It always follows. Cantor claimed it but couldn’t prove it. In 1897 the proof was found by the nineteen-year-old Felix Bernstein, a student in his seminar at Halle; Dedekind had proved the same thing back in 1887 but didn’t publish it.

If there are injections $f\colon A \to B$ and $g\colon B \to A$, then there’s a bijection between $A$ and $B$. In other words, $|A| \le |B|$ and $|B| \le |A|$ imply $|A| = |B|$.

The idea: from each element walk back along the arrows to its “ancestors”, and decide by where the chain of ancestors breaks off which arrow to pair it with.

The arrows of $f$ go down, from $A$ to $B$; the arrows of $g$ go up, from $B$ to $A$. Both are injective: at most one arrow enters each element.

From any element you can walk back along the incoming arrow, as long as there is one. The way back is unique, because there’s at most one incoming arrow. Forwards the way always continues. All the elements split into chains, and each chain is of one of four kinds: it starts in $A$ (its first element has no incoming arrow), starts in $B$, closes into a cycle, or is infinite in both directions.

In the chains that start in $A$, in cycles and in chains infinite both ways, pair each element $a \in A$ with its image $f(a)$. Each element of $B$ in such a chain has an ancestor in $A$, an incoming arrow of $f$, and gets exactly one partner.

In the chains that start in $B$, $f$ won’t do: the first element of $B$ would be left without a partner. Here pair each $a \in A$ with the unique $b$ from which the arrow of $g$ leads into it, that is, $g^{-1}(a)$. Every $a$ in such a chain does have an ancestor, since the chain starts in $B$.

The chains don’t overlap, and in each one the elements of $A$ and $B$ are split into pairs. Together this is a bijection between $A$ and $B$. Nothing had to be chosen: for every element the rule points to its partner unambiguously.

The theorem pays for itself at once. Let’s see how many subsets the natural numbers have.

All the subsets of the natural numbers. A subset is the same as an infinite string of zeros and ones: a one in place $k$ if $k$ belongs to the subset.

Notation in honour of the finite case: a set of $n$ elements has $2^n$ subsets. The strings of zeros and ones number “$2$ to the power countable”.

The points of a segment: binary fractions $0.b_1 b_2 b_3 \ldots_2$ with the same zeros and ones.

The continuum: the cardinality of the line.

Example: the subset $\{1, 3\}$ corresponds to the string $1010000\ldots$ and the binary number $0.101_2 = \frac12 + \frac18 = \frac58$; the subset of even numbers to the string $0101\ldots$ and the number $0.0101\ldots_2 = \frac13$.

$|\mathcal P(\mathbb N)| = |\mathbb R|$.

The idea: build two injections, one way through decimal fractions and the other through binary ones, and appeal to the Cantor–Bernstein theorem.

Assign to a subset $S \subset \mathbb N$ the number whose $k$th decimal digit after the point is $1$ if $k \in S$ and $0$ otherwise. Such a number’s digits are only zeros and ones, with no nines, so its decimal expansion is unique, and different subsets give different numbers: this is an injection $\mathcal P(\mathbb N) \to [0, 1]$. The other way: assign to a number $x \in [0, 1)$ the set of positions of the ones in its binary expansion, choosing the expansion that doesn’t end in an infinite tail of ones. Different numbers have different such expansions, and this is an injection $[0, 1) \to \mathcal P(\mathbb N)$. By the Cantor–Bernstein theorem $|\mathcal P(\mathbb N)| = |[0, 1)|$. Finally, $(0, 1) \subset [0, 1) \subset \mathbb R$, and $(0, 1)$ is equinumerous with $\mathbb R$; the embeddings give injections both ways, and by the same theorem again $|[0, 1)| = |\mathbb R|$.

Sagredo. And the square? A square must have the continuum squared points, that is, more.

Salviati. Cantor thought so too, and spent three years trying to prove it. Then in June 1877 he wrote to Dedekind that he’d proved the opposite, adding in French: “Je le vois, mais je ne le crois pas”, “I see it, but I don’t believe it”. Take a point $(x, y)$ of the square, with $0 \le x < 1$ and $0 \le y < 1$, and decimal expansions $x = 0.x_1 x_2 x_3 \ldots$ and $y = 0.y_1 y_2 y_3 \ldots$ without tails of nines, and interleave the digits: $0.x_1 y_1 x_2 y_2 x_3 y_3 \ldots$ Both coordinates can be recovered from this number, and it has no tail of nines. This is an injection of the square into the segment, and the segment embeds in the square as one of its sides. Then the Cantor–Bernstein theorem does its work: the square has as many points as the segment. So does a cube, and a space of any dimension.

Simplicio. But then there’s no difference between a line and a plane!

Salviati. Not in the number of points. The difference is in how the points are arranged: there’s no continuous bijection between a segment and a square. Dimension is a property not of cardinality but of shape, and the chapter on topology will tell you about it.

Now the whole ladder is visible. Start with $\aleph_0$ and keep taking power sets: $\aleph_0 < 2^{\aleph_0} = \mathfrak c < 2^{\mathfrak c} < 2^{2^{\mathfrak c}} < \dots$ The set of all functions from $\mathbb R$ to $\mathbb R$ is already on the second floor: its cardinality is $2^{\mathfrak c}$. Each floor is strictly higher than the one before by Cantor’s theorem, and there’s no top floor.

Day five. Dust

Sagredo. A countable set is thinner than the continuum. So if you throw away almost all the length of a segment, is what’s left countable?

Salviati. Let’s check. Throw away the middle third of the segment $[0, 1]$, the interval $(\frac13, \frac23)$. From each of the two remaining segments throw away the middle third again, and so on without end. What survives was described by Cantor in 1883; similar sets had been built before him by Henry Smith and Vito Volterra.

The Cantor set is the points of the segment $[0, 1]$ that remain after this operation is repeated without end. After $n$ steps $2^n$ segments of length $\frac1{3^n}$ are left.

Add steps of the construction and watch the length. Move a point along the segment or choose a number: the machine writes out its ternary expansion and says whether the point survives. Try $\frac14$.

The total length of the removed intervals is $1$, yet the Cantor set $C$ itself is equinumerous with the segment: $|C| = \mathfrak c$.

The idea: count the length with a geometric series, and the cardinality through ternary expansions: the points of $C$ are written with zeros and twos only, and if the twos are replaced by ones, you get the binary expansion of any point of the segment.

Length. At step $k$, $2^{k-1}$ intervals of length $\frac{1}{3^k}$ are removed, $\frac{2^{k-1}}{3^k}$ in all. The sum over all steps is a geometric series with first term $\frac13$ and ratio $\frac23$ (chapter 13): $\frac13 + \frac29 + \frac4{27} + \dots = \frac{1/3}{1 - 2/3} = 1$.

Cardinality. Write the points of the segment in base three: $x = 0.t_1 t_2 t_3 \ldots_3$ with $t_k \in \{0, 1, 2\}$. The first step removes the points whose first digit has to be a one, that is, the interval $(\frac13, \frac23)$. A point has survived $k - 1$ steps if its first $k - 1$ digits can be chosen from zeros and twos, and step $k$ removes those whose $k$th digit has to be a one. So $C$ is exactly the points that can be written without ones (endpoints like $\frac13 = 0.1_3 = 0.0222\ldots_3$ do have such an expansion). A point’s expansion in zeros and twos is unique. Assign to a binary string $b_1 b_2 b_3 \ldots$ the point $0.(2b_1)(2b_2)(2b_3)\ldots_3$ of the set $C$. Different strings give different points, so choosing one binary expansion for each point of the segment gives an injection $[0, 1] \to C$. And $C \subset [0, 1]$ gives an injection the other way. By the Cantor–Bernstein theorem $|C| = |[0, 1]| = \mathfrak c$.

The Cantor set contains no segment, not even a tiny one, its total “length” is zero, and yet it has as many points as the whole line. The number $\frac14 = 0.0202\ldots_3$ lies in it, though it’s not the endpoint of any removed interval. What “length zero” means for such a set, and how to measure the length of strange sets, is explained in the chapter on measure. And self-similarity (each piece is built like the whole, only three times smaller) will make the Cantor set the first exhibit in the chapter on fractals.

What is the total length of the segments left after five steps of building the Cantor set? Give the answer as a fraction.

After five steps there are $2^5 = 32$ segments of length $\frac{1}{3^5} = \frac{1}{243}$, $\frac{32}{243} \approx 0.13$ in all. Each step multiplies the length by $\frac23$, and $\left(\frac23\right)^5 = \frac{32}{243}$.

Day six. A question with no answer

Sagredo. Is there anything between $\aleph_0$ and $\mathfrak c$? A set on the line that’s bigger than countable but smaller than the continuum?

Salviati. Cantor conjectured in 1878 that there isn’t: every infinite subset of the line is either countable or equinumerous with the whole line. That’s the continuum hypothesis. He looked for a proof to the end of his life. In 1900 David Hilbert put it first on his list of problems for the new century.

The continuum hypothesis is the statement: there’s no set $X$ with $\aleph_0 < |X| < \mathfrak c$.

The answer came in two instalments, and it was one nobody expected. In 1940 Kurt Gödel showed that the continuum hypothesis can’t be refuted using the ZFC axioms from the last chapter: inside set theory he built a “world” in which all the axioms hold, and the hypothesis too. In 1963 Paul Cohen invented the method of forcing and built a world in which all the axioms hold and the hypothesis is false. So it can’t be proved from ZFC either. Both results hold on condition that ZFC itself is consistent. For this work Cohen received the Fields Medal in 1966.

Simplicio. In other words, you don’t know the answer.

Salviati. Worse, and more interesting: we know that our axioms don’t know it. A statement about sets of points on a line that the accepted rules don’t decide either way. You can add the hypothesis to the axioms, or add its negation: both paths are free of contradiction, if ZFC itself has none. Which axioms to regard as true, mathematicians still argue. And why arithmetic has true but unprovable statements is explained in the chapter on Gödel.

Sagredo. They say Cantor had a hard time during his life because of his infinities.

Salviati. He did. Leopold Kronecker considered his theory harmful, and many colleagues agreed. But in 1926 Hilbert wrote a sentence that everyone has quoted since: “No one shall expel us from the paradise that Cantor has created for us.”

Simplicio. A paradise where the hotel always has a free room. I might move there, as long as they don’t keep chasing me from room $n$ to room $n + 1$.

Simplicio’s homework

Three levels: find a position in a list, of the integers or of the hotel’s guests; find the number of a pair when walking along diagonals, and the pair from its number; and work out which infinity is in front of you: finite, countable, the continuum or bigger still.

Where next

The whole conversation rested on the real numbers. We took decimal expansions, glued $0.4999\ldots$ to $0.5$, squeezed nested intervals, called the line a “set of points”, and never once said what a real number is. In chapter 6 we honestly admitted that the definition was loose: how do you add infinite expansions if carries can come “from infinity”? In the nineteenth century it turned out that analysis couldn’t stand without a rigorous answer: there are continuous functions with no derivative at any point, and series of continuous functions converging to a discontinuous one. In 1872 Richard Dedekind built the real numbers from fractions, by cuts of the line. What a real number is, and which “obvious” facts of analysis had to be proved all over again, is chapter 53.