先来一个问题。正整数和偶数，哪个多？

直觉说正整数多，偶数只占一半。可如果把它们配成对：1 配 2，2 配 4，3 配 6，……每个正整数恰好配上一个偶数，谁也不落单。照这个配法，它们一样多。

这个别扭的现象，Galileo 在 1638 年的《两门新科学》里就写过：平方数 1, 4, 9, 16, … 越往后越稀，却能和全体正整数一个对一个地配齐。他的结论是，“相等”“更大”“更小”这些词，不能用在无穷上。

两百多年后，Cantor 反过来想：既然配对这么好用，干脆拿它来定义“一样多”。这一讲就从这个定义出发，看它能推出什么。需要的只是一点高中数学，加上反证法。

对有限集合，这就是“个数相等”。对无穷集合，这是唯一一个不需要“数完”就能比较的办法。照这个定义，下面四个集合和自然数集 $\mathbb{N}=\{0,1,2,\dots \}$ 一样大：

偶数只是 $\mathbb{N}$ 的一部分，却和整个 $\mathbb{N}$ 一样多。Dedekind 在 1888 年看出，这不是悖论，而恰好可以当作“无穷”的定义。他在书的脚注里说，1882 年 9 月就把这个定义告诉了 Cantor。

之前聊过的 Deutsch 书里那家“无穷旅馆”，说的就是这件事：所有房间都住满了，再来一位客人，就请 $n$ 号房的客人搬到 $n+1$ 号，空出 1 号房给新客。有限的旅馆做不到这一点，无穷的可以。

平面上的整点 $\mathbb{N}\times \mathbb{N}$ 呢？看起来比 $\mathbb{N}$ 多了一整个维度。

推论马上就来：有理数是可数的。把每个正有理数写成既约分数 $p/q$，对应到整点 $(p,q)$；不同的分数对应不同的点。可数集的子集要么有限、要么可数，再把 0 和负数交替插进去就行。

上面的排法要跳过重复的点（$2/4$ 和 $1/2$ 是同一个数），不够干净。2000 年，Calkin 和 Wilf 给了一个漂亮得多的排法。从 $1/1$ 出发，每个分数 $a/b$ 生两个孩子：左边是 $a/(a+b)$，右边是 $(a+b)/b$。

把这棵树一层一层读下来，得到 $1,\frac{1}{2},2,\frac{1}{3},\frac{3}{2},\frac{2}{3},3,\frac{1}{4},\dots$。更妙的是，后一项可以直接由前一项算出来：

这个公式归功于 Moshe Newman，2003 年发表在《美国数学月刊》一道题（Knuth 出的）的解答里。从 1 出发反复代入，你会一个不重、一个不漏地走遍所有正分数。本文脚本核对了前 8191 项：和按层读树的结果完全一致，两两不同。

所有有理数都是代数数，$\sqrt{2}$ 是 $x^2-2$ 的根，黄金比 $\phi$ 是 $x^2-x-1$ 的根。代数数在数轴上密密麻麻，可它们照样能排成一队。

到这里，你也许会猜：无穷都一样大，都能排成一队。Cantor 1874 年那篇论文的另一半，就是证明这个猜测是错的。

推论是：超越数存在，而且多得多。实数是代数数和超越数的并。代数数可数；如果超越数也可数，两个可数集交替着排，并起来还是可数，实数就可数了，矛盾。所以超越数不可数。

还可以说得更具体：代数数不但“少”，在长度的意义下简直不占地方。

这就是图 1·1 画的事。从 $[0,1]$ 里“随机”挑一个数，挑到代数数的概率是 0。我们从小认识的整数、分数、根号，在实数里只是一层几乎没有厚度的灰。

Liouville 和 Hermite、Lindemann 都是一个一个地造、一个一个地证，每一步都很费力。Cantor 换了一个问题：不去造，去数。

常有人说，Cantor 的证明是“非构造”的：只说存在，不告诉你是哪一个。其实不然。1994 年 Gray 专门写文章澄清：把代数数按高度明明白白排出来，再把对角线一位一位算下去，就能得到一个确定的超越数。只是这个数又难算又不好看，没人真想去算它。

再往前走一步。任何一个数，只要你能用一句有限长的话描述它，比如“圆周率”“2 的平方根”“$x^5-x-1=0$ 的实根”，这句话就是有限个字符排成的串。所有有限长的串可以先按长度、再按字典序排成一队，所以只有可数个。可是实数不可数。于是：几乎所有实数，人类永远叫不出它的名字。

实数比自然数多。有没有比实数还多的？有，而且永远有。

于是有一座没有顶的塔：

顺带一句，$\mathcal{P}(\mathbb{N})$ 和 $\mathbb{R}$ 一样大：把子集看成二进制小数的各位，0 表示不在、1 表示在。要严格证明，得处理 $0.0111\dots =0.1000\dots$ 这种重复，下一讲用 Schröder–Bernstein 定理一行就能证完。

Russell 读到 Cantor 定理时想到：所有集合组成的“集合” $V$，它的幂集应该比它大；可幂集里的元素都是集合，所以 $\mathcal{P}(V)\subseteq V$，矛盾。把上面证明里的 $f$ 换成恒等映射，$D$ 就成了 $\{x:x\notin x\}$，“所有不属于自己的集合”。1902 年他写信告诉 Frege，后者的《算术基本规律》第二卷正在付印。朴素集合论从此不得不改用公理来写，这是第四讲的伏笔。

这条对角线后来一次次出现：

取 $B=\{0,1\}$，$g$ 为“取反”。$g$ 没有不动点，所以不存在满射 $A\to \{0,1{\}}^A$。而 $\{0,1{\}}^A$ 就是 $A$ 的全体子集（用 0 和 1 标记在不在），这正是定理 6。Lawvere 在同一篇文章里还推出了 Russell、Gödel、Tarski 的结果；2003 年 Yanofsky 照这个路子，把停机问题和 Rice 定理也收了进来。之前提过的 Mac Lane 和这里的 Lawvere 都是范畴论学者，他们看数学，就是在找这种“同一个形状”。

这一讲只做了一件事：拿“能不能配对”去比较无穷。比出来的结果是两档。能排成一队的：自然数、整数、有理数、代数数。排不成的：实数、超越数、$\mathcal{P}(\mathbb{N})$。而且往上没有尽头。

我最喜欢的是 1874 年那一步。Cantor 证明超越数存在，没有比 Liouville 更聪明地去“造”，而是换了一个问题：数一数。数学里很多“存在”和“不可能”，都是这样换个问法得来的。

留两个问题给后面。实数轴 $\mathbb{R}$ 和平面 ${\mathbb{R}}^2$ 谁大？Cantor 1877 年得出答案时，自己都不敢相信，这是下一讲的事。还有，$\mathbb{N}$ 和 $\mathbb{R}$ 之间，有没有第三种大小？这就是第四讲的连续统假设。

没有人能把我们
从 Cantor 为我们创造的乐园中
赶出去。
Hilbert，《论无穷》（1926）

A question to start. Which are there more of, positive integers or even numbers?

Intuition says positive integers: the even numbers are only half of them. But pair them up: 1 with 2, 2 with 4, 3 with 6, … Every positive integer gets exactly one even number, and nobody is left without a partner. By this pairing, there are just as many of each.

Galileo had already described this awkward fact in 1638, in “Two New Sciences”: the squares 1, 4, 9, 16, … grow sparser and sparser, yet they can be matched one-to-one with all the positive integers. His conclusion was that words like “equal,” “greater” and “less” cannot be applied to the infinite.

More than two hundred years later, Cantor turned this around: since pairing works so well, why not use it to define “as many”? This lecture starts from that definition and sees what follows from it. All you need is a little high-school mathematics and proof by contradiction.

For finite sets this just means “having the same number of elements.” For infinite sets it is the only way to compare them without “counting to the end.” By this definition, the four sets below are all the same size as the set of natural numbers $\mathbb{N}=\{0,1,2,\dots \}$:

The even numbers are only part of $\mathbb{N}$, yet there are just as many of them as there are in the whole of $\mathbb{N}$. In 1888 Dedekind saw that this is no paradox: it can serve as the very definition of “infinite.” In a footnote to his book he says that he had told Cantor this definition in September 1882.

The “infinite hotel” in Deutsch's book, which came up before, is exactly this. Every room is taken, a new guest arrives, and the guest in room $n$ is asked to move to room $n+1$, which frees room 1 for the newcomer. A finite hotel cannot do this; an infinite one can.

What about the lattice points of the plane, $\mathbb{N}\times \mathbb{N}$? They seem to have a whole extra dimension compared with $\mathbb{N}$.

A corollary follows at once: the rational numbers are countable. Write each positive rational number as a fraction in lowest terms, $p/q$, and send it to the lattice point $(p,q)$; different fractions go to different points. A subset of a countable set is either finite or countable; after that, just slip in 0 and the negatives, alternating with the positives.

The listing above has to skip repeated points ($2/4$ and $1/2$ are the same number), which is not very clean. In 2000 Calkin and Wilf gave a much prettier one. Start from $1/1$; every fraction $a/b$ has two children, $a/(a+b)$ on the left and $(a+b)/b$ on the right.

Read the tree level by level and you get $1,\frac{1}{2},2,\frac{1}{3},\frac{3}{2},\frac{2}{3},3,\frac{1}{4},\dots$. Better still, each term can be computed directly from the one before it:

This formula is due to Moshe Newman; it appeared in 2003 in the solution to a problem (posed by Knuth) in the American Mathematical Monthly. Start from 1 and keep applying it, and you will walk through every positive fraction, missing none and repeating none. This article's script checked the first 8191 terms: they match the level-by-level reading of the tree exactly, and no two are equal.

Every rational number is algebraic; $\sqrt{2}$ is a root of $x^2-2$, and the golden ratio $\phi$ is a root of $x^2-x-1$. The algebraic numbers crowd the number line, yet they too can be lined up.

By now you might guess that all infinities are the same size, and that they can all be lined up. The other half of Cantor's 1874 paper proves that guess wrong.

The corollary: transcendental numbers exist, and there are far more of them. The reals are the union of the algebraic and the transcendental numbers. The algebraic numbers are countable; if the transcendental numbers were countable too, you could interleave the two lists and the union would still be countable, so the reals would be countable, a contradiction. So the transcendental numbers are uncountable.

We can say something more concrete: the algebraic numbers are not just “fewer”; in the sense of length, they take up no room at all.

This is what Figure 1·1 shows. Pick a number “at random” from $[0,1]$, and the probability of picking an algebraic number is 0. The integers, fractions and square roots we have known since childhood are, among the reals, only a film of dust with almost no thickness.

Liouville, Hermite and Lindemann built them one at a time and proved them one at a time, and every step took a great deal of work. Cantor changed the question: don't build, count.

People often say that Cantor's proof is “non-constructive”: it says one exists without telling you which. Not so. In 1994 Gray wrote a paper specifically to set the record straight: list the algebraic numbers explicitly by height, then compute the diagonal digit by digit, and you get a definite transcendental number. It is just that the number is hard to work out and not pretty, so nobody really wants to.

One step further. Any number you can describe in a sentence of finite length, such as “pi,” “the square root of 2” or “the real root of $x^5-x-1=0$,” is described by a string of finitely many characters. All finite strings can be lined up, first by length and then alphabetically, so there are only countably many of them. But the reals are uncountable. So almost every real number is one that humans will never be able to name.

There are more reals than natural numbers. Is there anything with even more elements than the reals? Yes, and there always is.

So there is a tower with no top:

Incidentally, $\mathcal{P}(\mathbb{N})$ and $\mathbb{R}$ are the same size: think of a subset as the digits of a binary fraction, 0 for “not in” and 1 for “in.” A rigorous proof has to deal with duplicates like $0.0111\dots =0.1000\dots$; in the next lecture, the Cantor–Schröder–Bernstein theorem will settle it in one line.

When Russell read Cantor's theorem, he thought of this: the “set” of all sets, $V$, should have a power set bigger than itself; but the elements of the power set are all sets, so $\mathcal{P}(V)\subseteq V$, a contradiction. Replace $f$ in the proof above by the identity map, and $D$ becomes $\{x:x\notin x\}$, “the set of all sets that do not belong to themselves.” In 1902 he wrote to tell Frege, whose “Basic Laws of Arithmetic,” volume II, was then at the printer. From then on, naive set theory had to be rebuilt on axioms, which sets the stage for Lecture 4.

This diagonal later turned up again and again:

Take $B=\{0,1\}$, and let $g$ be negation. $g$ has no fixed point, so there is no surjection $A\to \{0,1{\}}^A$. And $\{0,1{\}}^A$ is just the set of all subsets of $A$ (with 0 and 1 marking “out” and “in”), so this is exactly Theorem 6. In the same paper Lawvere also derived the results of Russell, Gödel and Tarski; in 2003 Yanofsky followed the same path and brought in the halting problem and Rice's theorem as well. Mac Lane, who came up in an earlier essay, and Lawvere here are both category theorists; for them, looking at mathematics means looking for this kind of “same shape.”

This lecture did one thing: it compared infinities by asking whether they can be paired up. The comparison gives two tiers. Those that can be lined up: the natural numbers, the integers, the rationals, the algebraic numbers. Those that cannot: the reals, the transcendental numbers, $\mathcal{P}(\mathbb{N})$. And going up, there is no end.

My favorite step is the one from 1874. To prove that transcendental numbers exist, Cantor did not try to out-clever Liouville at “building” them; he changed the question and counted. Many of the “there exists” and “it is impossible” results in mathematics came about in just this way, by asking the question differently.

Two questions for later. Which is bigger, the real line $\mathbb{R}$ or the plane ${\mathbb{R}}^2$? When Cantor found the answer in 1877, he could hardly believe it himself; that is for the next lecture. And is there a third size between $\mathbb{N}$ and $\mathbb{R}$? That is the continuum hypothesis, in Lecture 4.

No one shall expel us
from the paradise
that Cantor has created.
Hilbert, “On the Infinite” (1926)