上一讲留了一道题：用 Newman 公式从 1 开始算，第 2026 项是哪个分数？答案是 $33/53$。

不必真的迭代两千多次。把 2026 写成二进制：$2026=(11111101010{)}_2$。去掉打头的 1，剩下的位从左往右读：1 就往右孩子走，0 就往左孩子走。从树根 $1/1$ 出发走十步，正好停在 $33/53$。

为什么能这样走？树按层编号，第 $n$ 个节点的左孩子是第 $2n$ 个、右孩子是第 $2n+1$ 个，和二进制在末尾添一位 0 或 1 完全一样。

1874 年 1 月 5 日，Cantor 写信问 Dedekind：一个正方形（连同它的边界）能不能和一条线段（连同端点）一一对应？他自己的直觉是不能，平面看起来“多了一整个维度”，几乎所有人都会这么想。Dedekind 没有回答，同年 5 月他又问了一次。

三年后，他亲手推翻了这个直觉。

最朴素的想法是把 $x$ 和 $y$ 的小数位一位一位交替排：$x=0.x_1{x}_2{x}_3\dots$，$y=0.y_1{y}_2{y}_3\dots$，令 $z=0.x_1{y}_1{x}_2{y}_2{x}_3{y}_3\dots$。1877 年 6 月 20 日，Cantor 寄给 Dedekind 的证明就是这个思路。

两天后 Dedekind 回信指出一个漏洞。有些数有两种小数写法，比如 $0.3=0.2999\dots$，Cantor 约定一律写成无穷小数（不以 0 结尾）。这样定义的映射是单射，却不是满射：如果 $z$ 从某一位起，奇数位全是 0，拆出来的 $x$ 就是有限小数，恰好是被约定排除的写法，$z$ 没有原像。

Cantor 第二天回了一张明信片，大意是：您说得完全对，好在这只打中了证明，没打中结论本身。6 月 25 日他寄出新证明，改用连分数，绕开了小数的双重写法。今天教科书里常用下面这个更简单的补法，据说来自 König。

切成块，而不是一位一位地切，妙处在于：每块都以非零数字结尾，所以拼起来的数永远不会落进“无穷个 0 结尾”的那种写法。漏洞没了。同样的办法对 $n$ 个坐标也成立，所以线段、正方形、立方体，乃至任意有限维的空间，点都一样多。

1877 年 6 月 29 日，Cantor 又写信催 Dedekind 检查新证明。信是德文写的，大意是：这些结果连我自己都觉得太意外、太新，您没给我判断之前，我心里静不下来。在您同意之前，我只能说一句法语：

这句话常被讲成“Cantor 被自己的结论吓坏了”。2011 年，Gouvêa 专门写文章考证上下文，认为不是这么回事：Cantor 在信里明说自己对结论早有信念，他是在催 Dedekind 帮他确认证明有没有错。前一个证明刚被挑出漏洞，他对新证明还不放心。“不信”的是证明，不是定理。

如果线段和正方形的点一样多，“维数”还有什么意义？7 月 2 日 Dedekind 回信：新证明他查过了，没找到漏洞。但他相信，维数不同的空间之间的一一对应，必然处处不连续；维数仍是这类空间“第一重要的不变量”。上面那个对应确实把相邻的点撕得七零八落。

这个“挖一个点”的论证只能区分 1 维和更高维。要证明 ${\mathbb{R}}^m$ 和 ${\mathbb{R}}^n$（$m\ne n$）都不同胚，难得多。Netto、Cantor 等人在 1879 年前后都试过一般情形，后来发现证明各有漏洞；Netto 证对了的是 1 维对 2 维：线段和正方形之间连连续的双射都没有，不需要逆也连续。一般情形直到 1911 年才由 Brouwer 完成。

可连续的满射是有的。1890 年 Peano 构造了一条连续曲线，填满整个正方形；第二年 Hilbert 给了一个更直观的版本：

所以，“一样多”“连续地满”“连续地一一对应”是三件不同的事。前两件线段和正方形都做得到，第三件做不到，维数就藏在这里。

定理 1 要亲手造出一个双射，还得小心翼翼地补漏洞。有没有更省事的判别法？

对有限集合，这件事显然：$A$ 能单射进 $B$，$B$ 也能单射进 $A$，那它们个数相等。对无穷集合，这一点也不显然，偶数能塞进整数，整数也能塞进偶数，可塞的方式各不相同，拼不成一个双射。下面这条定理说：没关系，总能拼出来。

这个定理的名字记错了人。Cantor 1887 年就陈述过它，1895 年又把它列为“任何两个基数都可比”的推论，留待以后证明。Dedekind 1887 年 7 月写下过一个证明，但只留在手稿里，1932 年才印出来。Schröder 1896 年宣布了一个证明，1902 年 Korselt 写信指出其中有漏洞，Schröder 当即承认。差不多同时，19 岁的 Bernstein 在 Cantor 于哈雷的讨论班上给出了正确的证明，1898 年由 Borel 写进书里。上面这个按“链”分类的证明，是 König 1906 年给的。

$[0,1]$ 和 $[0,1)$ 一样多吗？两头的单射都现成：$[0,1)\to [0,1]$ 用包含映射，$[0,1]\to [0,1)$ 用 $x\mapsto x/2$。按上面的证明把链找出来，得到的双射是：把 $1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots$ 各往后挪一格，其余的点原地不动。

有了定理 3，证明“一样多”就只需要找两个单射，容易多了。实数的个数记作 $\mathfrak{c}$（花体的 c，continuum），也写作 $2^{{\aleph }_0}$，原因马上就清楚。

一个子集就是一列“在 / 不在”的选择，所以 $|\mathcal{P}(\mathbb{N})|$ 记作 $2^{{\aleph }_0}$，于是 $\mathfrak{c}=2^{{\aleph }_0}$。

从 $[0,1]$ 里挖掉中间的三分之一，剩下两段再各挖掉中间三分之一，无限做下去，剩下的点组成 Cantor 集。

上一讲说可数集“几乎不占地方”。Cantor 集说明反过来不对：一个集合可以长度为零，却和整条实数轴一样多。“多少”和“多长”是两回事。

这是一个纯粹靠“数个数”得到的存在性证明，和上一讲 Cantor 证明超越数存在一模一样：一个也没造出来，却知道它们多得是。

到目前为止，我们比较的集合都能找到单射。可是，任给两个集合 $A$、$B$，一定有一个能单射进另一个吗？对有限集合这是废话，对无穷集合，答案出人意料：这件事证不出来，除非你接受一条额外的公理。

挑有限次，不需要这条公理。麻烦在于同时挑无穷多次、又说不出挑选的规则。1904 年 Zermelo 用它证明：任何集合都能良序，也就是排成一队，使得任何非空子集都有“排在最前”的元素。下一讲就讲这种“队”，它就是序数。

反过来，选择公理也推出任何两个集合都能比。所以下面几件事在 ZF 公理系统里互相等价：

最后一条最有意思。定理 1 和上一讲的配对函数，说的是 $\mathbb{R}$ 和 $\mathbb{N}$ 平方以后不变大。Tarski 证明：要让所有无穷集合都有这个性质，选择公理一点都少不了。

这一讲比的是“大小”，得到的是三层意思。第一，维数不是点的多少，而是连续结构的性质：线段和正方形一样多，却不同胚。第二，比较无穷有一个好用的判别法：两头都塞得进，就一样多。第三，“任何两个无穷都能比”本身不是白给的，它和选择公理是同一件事。

表里的三档，${\aleph }_0<\mathfrak{c}<2^{\mathfrak{c}}$，留下一个最自然的问题：${\aleph }_0$ 和 $\mathfrak{c}$ 之间，还有没有别的大小？Cantor 在 1878 年那篇论文的结尾已经猜过：直线上的无穷子集只有两种大小，要么可数，要么和整条直线一样多。要回答它，先得学会“数”到无穷之后：下一讲讲序数，$\omega$、$\omega +1$、${\omega }^2$，以及一个只要你会加减法就能读懂、却在普通算术里证不出来的定理。

点的多少，和点怎么挨在一起，
是两回事。

Last lecture left a puzzle: starting from 1 with Newman's formula, which fraction is the 2026th term? The answer is $33/53$.

There is no need to actually iterate more than two thousand times. Write 2026 in binary: $2026=(11111101010{)}_2$. Drop the leading 1 and read the remaining bits from left to right: 1 means go to the right child, 0 means go to the left child. Starting from the root $1/1$, ten steps land you exactly on $33/53$.

Why does this work? Number the nodes of the tree level by level: the left child of node $n$ is node $2n$ and its right child is node $2n+1$, exactly like appending a 0 or a 1 to the end of a binary number.

On January 5, 1874, Cantor wrote to ask Dedekind: can a square (with its boundary) be put in one-to-one correspondence with a line segment (with its endpoints)? His own intuition said no: the plane seems to have “a whole extra dimension,” and nearly everyone would think the same. Dedekind did not answer, and in May of that year Cantor asked again.

Three years later, he overturned that intuition himself.

The most naive idea is to interleave the decimal digits of $x$ and $y$ one at a time: $x=0.x_1{x}_2{x}_3\dots$, $y=0.y_1{y}_2{y}_3\dots$, and let $z=0.x_1{y}_1{x}_2{y}_2{x}_3{y}_3\dots$. The proof Cantor sent Dedekind on June 20, 1877, followed this idea.

Two days later Dedekind wrote back pointing out a gap. Some numbers have two decimal expansions, such as $0.3=0.2999\dots$, and Cantor's convention was to always use the infinite expansion (the one that does not end in 0s). The map defined this way is injective but not surjective: if from some point on all the odd-numbered digits of $z$ are 0, then the $x$ extracted from it is a terminating decimal, exactly the kind of expansion the convention ruled out, and so $z$ has no preimage.

Cantor replied the next day with a postcard, saying in effect: you are quite right, but fortunately the objection hits only the proof, not the result itself. On June 25 he sent a new proof that used continued fractions, sidestepping the double expansions of decimals. Textbooks today usually give the simpler fix below, said to be due to König.

The beauty of cutting into blocks, rather than digit by digit, is this: every block ends in a nonzero digit, so the number you assemble can never fall into the kind of expansion that “ends in infinitely many 0s.” The gap is gone. The same trick works for $n$ coordinates, so a segment, a square, a cube, indeed a space of any finite dimension, all have equally many points.

On June 29, 1877, Cantor wrote again, urging Dedekind to check the new proof. The letter was in German, and said in effect: these results are so unexpected and so new, even to me, that I cannot be at peace until you have given me your verdict. Until you agree, all I can say is a sentence in French:

This line is often taken to mean that “Cantor was frightened by his own result.” In 2011 Gouvêa wrote a paper looking closely at the context and concluded that this is not what happened: in the letter Cantor says plainly that he had long been convinced of the result; he was urging Dedekind to help confirm whether the proof had a mistake. His previous proof had just been shown to have a gap, and he was not yet sure of the new one. What he “didn't believe” was the proof, not the theorem.

If a segment and a square have equally many points, what is left of “dimension”? On July 2 Dedekind replied: he had checked the new proof and found no gap. But he believed that any one-to-one correspondence between spaces of different dimensions must be discontinuous everywhere, and that dimension was still “the most important invariant” of such spaces. The correspondence above does indeed tear neighboring points far apart.

This “remove a point” argument can only tell dimension 1 apart from higher dimensions. Proving that ${\mathbb{R}}^m$ and ${\mathbb{R}}^n$ are never homeomorphic (for $m\ne n$) is much harder. Netto, Cantor and others tried the general case around 1879, and their proofs were later found to have gaps; what Netto did prove correctly was dimension 1 versus dimension 2: between a segment and a square there is not even a continuous bijection, never mind one with a continuous inverse. The general case was settled only in 1911, by Brouwer.

Continuous surjections, though, do exist. In 1890 Peano constructed a continuous curve that fills the whole square; the next year Hilbert gave a more intuitive version:

So “equally many,” “continuously onto” and “continuously one-to-one” are three different things. A segment and a square can manage the first two, but not the third, and that is where dimension hides.

Theorem 1 meant building a bijection by hand and carefully patching a gap. Is there a less laborious test?

For finite sets the answer is obvious: if $A$ injects into $B$ and $B$ also injects into $A$, they have the same number of elements. For infinite sets it is not obvious at all. The even numbers fit into the integers, and the integers fit into the even numbers, but the two ways of fitting are different and do not combine into a bijection. The theorem below says: never mind, you can always piece one together.

This theorem's name credits the wrong people. Cantor stated it as early as 1887, and in 1895 he listed it as a corollary of “any two cardinals are comparable,” leaving the proof for later. Dedekind wrote down a proof in July 1887, but it stayed among his manuscripts and was not printed until 1932. Schröder announced a proof in 1896; in 1902 Korselt wrote to point out a gap in it, and Schröder admitted it at once. At about the same time, the 19-year-old Bernstein gave a correct proof in Cantor's seminar in Halle, and Borel put it in his book in 1898. The proof above, which sorts everything into “chains,” was given by König in 1906.

Do $[0,1]$ and $[0,1)$ have equally many points? Injections both ways are ready to hand: for $[0,1)\to [0,1]$ use the inclusion map, and for $[0,1]\to [0,1)$ use $x\mapsto x/2$. Find the chains as in the proof above, and the bijection you get is this: move each of $1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\dots$ one place along the list, and leave all the other points where they are.

With Theorem 3, proving “equally many” only takes finding two injections, which is much easier. The number of real numbers is written $\mathfrak{c}$ (a Fraktur c, for continuum), and also $2^{{\aleph }_0}$; the reason will be clear in a moment.

A subset is a sequence of “in / out” choices, so $|\mathcal{P}(\mathbb{N})|$ is written $2^{{\aleph }_0}$, and hence $\mathfrak{c}=2^{{\aleph }_0}$.

Remove the middle third of $[0,1]$, then remove the middle third of each of the two pieces left, and keep going forever; the points that remain form the Cantor set.

Last lecture said that countable sets “take up almost no room.” The Cantor set shows that the converse is false: a set can have length zero and still have as many points as the whole real line. “How many” and “how long” are two different things.

This is an existence proof obtained purely by “counting,” exactly like Cantor's proof last lecture that transcendental numbers exist: not a single one has been built, yet we know there are plenty of them.

So far, for every pair of sets we compared, we could find the injections. But given any two sets $A$ and $B$, must one of them inject into the other? For finite sets this goes without saying. For infinite sets the answer is a surprise: it cannot be proved, unless you accept one extra axiom.

Picking finitely many times needs no such axiom. The trouble comes with picking infinitely many times at once, with no rule you can state for how to pick. In 1904 Zermelo used it to prove that every set can be well-ordered, that is, lined up so that every nonempty subset has an element that comes “first.” The next lecture is about these line-ups, which are the ordinals.

Conversely, the axiom of choice also implies that any two sets can be compared. So the following are all equivalent in the ZF axioms:

The last one is the most interesting. Theorem 1 and last lecture's pairing function say that $\mathbb{R}$ and $\mathbb{N}$ do not get any bigger when squared. Tarski proved that for every infinite set to have this property, you need the axiom of choice in full.

This lecture compared “sizes,” and came away with three lessons. First, dimension is not a matter of how many points there are but a property of continuous structure: a segment and a square have equally many points, yet they are not homeomorphic. Second, there is a handy test for comparing infinities: if each fits into the other, they are the same size. Third, “any two infinities can be compared” does not come for free; it is the same thing as the axiom of choice.

The three tiers of the table, ${\aleph }_0<\mathfrak{c}<2^{\mathfrak{c}}$, leave one very natural question: is there any other size between ${\aleph }_0$ and $\mathfrak{c}$? Cantor had already made a guess at the end of his 1878 paper: infinite subsets of the line come in only two sizes, either countable or the same size as the whole line. To answer it, we first have to learn to “count” past infinity. The next lecture is about ordinals such as $\omega$, $\omega +1$ and ${\omega }^2$, and about a theorem that anyone who can add and subtract can understand, yet that cannot be proved in ordinary arithmetic.

How many points there are, and how they sit next to one another,
are two different things.