先写成“不以无穷个 0 结尾”的小数：$\frac{1}{2}=0.4999\dots$，切块是 $4|9|9\dots$；$\frac{1}{4}=0.24999\dots$，切块是 $2|4|9\dots$。交替排起来：

Cantor 不是为了好玩才去数无穷的。1870 年前后他研究三角级数：一个函数的三角级数展开唯一吗？他证明，就算在一些例外点上不知道级数收不收敛，只要这些例外点不太多，展开仍然唯一。“不太多”怎么量？他想出一个办法：从一个点集 $P$ 里删掉孤立点，得到 $P^{\prime }$；再删一次，得到 $P^{\prime \prime }$；如此下去。

有的点集删有限次就空了。有的删了 $P^{\prime },P^{\prime \prime },P^{\prime \prime \prime },\dots$ 无穷多次还剩下一些点。1880 年，Cantor 把剩下的公共部分叫 $P^{(\infty )}$，然后接着删：$P^{(\infty +1)}$，$P^{(\infty +2)}$，……，$P^{({\infty }^2)}$，$P^{({\infty }^{\infty })}$。那时它们还只是“无穷的记号”。1883 年他把它们正式立成一种数，并在脚注里说，从今以后把 $\infty$ 改记作 $\omega$。

“接着数”要有一个前提：任何时候，“下一个”都得是确定的。这就是良序。

这条定理是整讲的发动机：在良序里，往下走，必然在有限步内走到底。哪怕这个良序本身长得吓人。Cantor 1883 年就写过同样的话：这些新数组成的递减序列，必然在有限多项后中断。

两个良序集，如果存在保持顺序的双射，就说它们“同型”。序数就是良序的“型”，好比基数是集合的“大小”。1923 年 von Neumann 给了一个干净的定义，让每个型都有一个标准代表：

普通的数学归纳法只走到 $\omega$。超限归纳能走过 $\omega$，因为它不需要“前一个”：像 $\omega$ 这样的极限序数没有前一个，但“所有比它小的”总是有的。

序数的加法就是“接起来排”：$\alpha +\beta$ 是先排一个 $\alpha$，后面再接一个 $\beta$。

乘法也一样：$2\cdot \omega$ 是“$\omega$ 个 2 接起来”，还是 $\omega$；$\omega \cdot 2$ 是“两个 $\omega$ 接起来”，比 $\omega$ 大。作为基数，$\omega$、$\omega +1$、$\omega \cdot 2$、${\omega }^2$ 都是 ${\aleph }_0$，都可数；作为序数，它们是不同的“长度”。

就像每个正整数都能唯一地写成 $b$ 进制，每个序数也能唯一地写成“$\omega$ 进制”。

“范式”这个名字和下面的记号都是 Cantor 1897 年起的。指数 ${\beta }_i$ 本身也能再写成范式，于是出现幂塔：${\omega }^{\omega }$，${\omega }^{{\omega }^{\omega }}$，…… 这一串的极限记作 ${\epsilon }_0$，它满足 ${\omega }^{{\epsilon }_0}={\epsilon }_0$。Cantor 把满足 ${\omega }^{\xi }=\xi$ 的数叫 $\epsilon$ 数，${\epsilon }_0$ 是其中最小的，也是第一个让“写成 $\omega$ 进制”失去意义的序数。

下面这个游戏只用到加减法和乘方。先说“递归 $b$ 进制”：把一个数写成 $b$ 进制，再把指数也写成 $b$ 进制，指数的指数也一样，直到所有数字都小于 $b$。比如

规则是：把底数 $b$ 处处换成 $b+1$，然后减 1。这叫一步。从底数 2 开始，一步一步做下去，得到的数列叫 Goodstein 序列。

从 3 出发很平淡：

从 4 出发就完全不一样了：

这个序列会涨到大得不可想象，然后回落。本文脚本把它分段推了一遍（推法先在小例子上和逐步模拟对过）：它在底数 $3\cdot 2^{402653211}-1$ 时恰好归零，也就是走了 $3\cdot 2^{402653211}-3$ 步，连头带尾一共 $3\cdot 2^{402653211}-2$ 项。这和 Kirby、Paris 1982 年论文里给的数一致。这个数有大约一亿两千万位。

数在涨，影子在降。底数每一步只加 1，这个“加 1”被 $\omega$ 吸收掉了；减掉的 1，却实实在在地从影子上削下一块。Goodstein 1944 年其实证得更一般：底数每步换成任何不减的整数函数都行。“每步加 1”这个最简单的版本，是后来 Kirby 和 Paris 拿出来讲的。

定理 6 的叙述里只有自然数和加减乘方，可证明用到了无穷序数。能不能只用自然数的推理把它证出来？

Kirby 和 Paris 同时给了一个更形象的版本：Hercules 砍九头蛇。蛇是一棵树，每次砍掉一个头，蛇就会从被砍处的“爷爷”那里长出若干份新的拷贝，而且每一轮长得更多。不管怎么砍，Hercules 最后一定赢。这件事同样用序数一证就出来，同样在 Peano 算术里证不出来。

这类结果的意义在于：哥德尔告诉我们，足够强的形式系统里总有证不出来的真命题，但他造的那个句子是专门绕出来的。Goodstein 定理是一个数学家自然会问、而且确实为真的关于自然数的命题，只是证明它必须“借道”无穷。Kirby 和 Paris 在论文里说，这也许是第一个纯数论的这类例子；稍早的 1977 年，Paris 和 Harrington 给过一个组合学的例子。

$\omega$、${\omega }^2$、${\epsilon }_0$ 都可数。有没有不可数的序数？把所有可数序数放在一起，记作 ${\omega }_1$。它是一个良序集，所以是一个序数；它不可能可数，否则它就是自己的一个元素，比自己还小。于是 ${\omega }_1$ 是第一个不可数序数，它的基数记作 ${\aleph }_1$。

${\omega }_1$ 有多“长”？实数轴装不下它：

所以 ${\aleph }_1$ 是一种“看不见的”大小：在选择公理下 ${\aleph }_1\le 2^{{\aleph }_0}$，可你没法在实数轴上按大小顺序把它排出来。

ℵ 一路往上：${\aleph }_0,{\aleph }_1,{\aleph }_2,\dots ,{\aleph }_{\omega },\dots$，每个无穷基数（在选择公理下）都在这张表里。而上一讲那三档里的 $\mathfrak{c}=2^{{\aleph }_0}$ 在哪？它是 ${\aleph }_1$ 吗？

这一讲做了两件事。一是学会了“数”到无穷之后：良序保证了“下一个”总是确定的，序数就是良序的长度，超限归纳让我们能走过任何极限。二是看到这种无穷有一个非常具体的用处：Goodstein 序列涨到天文数字又落回 0，证明它只需要一句“序数不能无穷下降”；可不借道无穷，算术就证不出来。

$2^{{\aleph }_0}$ 是不是 ${\aleph }_1$？这就是 1878 年 Cantor 猜过、1900 年 Hilbert 列为二十三个问题之首的连续统假设。下一讲会看到，它的答案不是“是”，也不是“不是”。

数在涨，影子在降；
而影子不能永远降下去。

First write both as decimals that “do not end in infinitely many 0s”: $\frac{1}{2}=0.4999\dots$, cut into blocks as $4|9|9\dots$; and $\frac{1}{4}=0.24999\dots$, cut into blocks as $2|4|9\dots$. Interleave them:

Cantor did not count into the infinite for fun. Around 1870 he was studying trigonometric series: is the trigonometric series expansion of a function unique? He proved that even if you do not know whether the series converges at certain exceptional points, the expansion is still unique, as long as there are not too many exceptional points. How do you measure “not too many”? He came up with a method: remove the isolated points from a point set $P$ to get $P^{\prime }$; remove them again to get $P^{\prime \prime }$; and so on.

Some point sets become empty after finitely many removals. Others still have points left after infinitely many, $P^{\prime },P^{\prime \prime },P^{\prime \prime \prime },\dots$. In 1880 Cantor called the common part that remains $P^{(\infty )}$, and then kept on removing: $P^{(\infty +1)}$, $P^{(\infty +2)}$, …, $P^{({\infty }^2)}$, $P^{({\infty }^{\infty })}$. At the time these were still just “symbols for the infinite.” In 1883 he formally established them as a kind of number, and said in a footnote that from then on he would write $\infty$ as $\omega$.

“Counting on” needs one thing: at every stage, “the next one” must be determined. That is what well-ordering means.

This theorem is the engine of the whole lecture: in a well-ordering, if you keep stepping down, you must hit bottom in finitely many steps, however frighteningly long the well-ordering itself may be. Cantor said the same thing in 1883: a decreasing sequence of these new numbers must break off after finitely many terms.

If there is an order-preserving bijection between two well-ordered sets, we say they have the same “type.” An ordinal is the “type” of a well-ordering, much as a cardinal is the “size” of a set. In 1923 von Neumann gave a clean definition that provides every type with a standard representative:

Ordinary mathematical induction only takes you up to $\omega$. Transfinite induction can go past $\omega$, because it does not need “the one before”: a limit ordinal like $\omega$ has no “one before,” but “all the ones smaller than it” are always there.

Adding ordinals means “placing one after the other”: $\alpha +\beta$ means first lay out an $\alpha$, then put a $\beta$ after it.

Multiplication is the same: $2\cdot \omega$ is “$\omega$ copies of 2 placed end to end,” which is still $\omega$; $\omega \cdot 2$ is “two copies of $\omega$ placed end to end,” which is bigger than $\omega$. As cardinals, $\omega$, $\omega +1$, $\omega \cdot 2$ and ${\omega }^2$ are all ${\aleph }_0$, all countable; as ordinals they are different “lengths.”

Just as every positive integer can be written uniquely in base $b$, every ordinal can be written uniquely “in base $\omega$.”

Both the name “normal form” and the notation below were introduced by Cantor in 1897. The exponents ${\beta }_i$ can themselves be written in normal form, and so power towers appear: ${\omega }^{\omega }$, ${\omega }^{{\omega }^{\omega }}$, … The limit of this sequence is written ${\epsilon }_0$, and it satisfies ${\omega }^{{\epsilon }_0}={\epsilon }_0$. Cantor gave the name $\epsilon$-numbers to the numbers satisfying ${\omega }^{\xi }=\xi$; ${\epsilon }_0$ is the smallest of them, and also the first ordinal for which “writing it in base $\omega$” stops meaning anything.

The game below uses only addition, subtraction and powers. First, “hereditary base-$b$ notation”: write a number in base $b$, then write the exponents in base $b$ as well, and the exponents of the exponents, and so on, until every number that appears is less than $b$. For example:

The rule: replace the base $b$ everywhere by $b+1$, then subtract 1. That is one step. Start with base 2 and keep taking steps; the resulting sequence of numbers is called a Goodstein sequence.

Starting from 3, nothing much happens:

Starting from 4, it is a completely different story:

This sequence grows unimaginably large, and then comes back down. This article's script pushed it all the way through in stages (the method was first checked against step-by-step simulation on small cases): it reaches zero exactly when the base is $3\cdot 2^{402653211}-1$, that is, after $3\cdot 2^{402653211}-3$ steps, or $3\cdot 2^{402653211}-2$ terms counting both ends. This agrees with the figure given in Kirby and Paris's 1982 paper. That number has about 120 million digits.

The number goes up, the shadow goes down. The base grows by only 1 at each step, and this “plus 1” is absorbed by $\omega$; the 1 subtracted, though, carves a real piece off the shadow. Goodstein actually proved something more general in 1944: the new base at each step can be given by any non-decreasing integer function. The simplest version, “add 1 at each step,” is the one Kirby and Paris later singled out.

The statement of Theorem 6 involves only natural numbers, addition, subtraction and powers, but the proof used infinite ordinals. Can it be proved by reasoning about natural numbers alone?

Kirby and Paris also gave a more vivid version: Hercules fighting the Hydra. The Hydra is a tree; each time a head is cut off, the Hydra grows several new copies from the “grandparent” of the severed head, and more copies each round. However Hercules chops, he wins in the end. This too follows in a stroke from ordinals, and this too cannot be proved in Peano arithmetic.

Why results like this matter: Gödel showed that any sufficiently strong formal system has true statements it cannot prove, but the sentence he built was contrived for the purpose. Goodstein's theorem is a statement about natural numbers that a mathematician might naturally ask, and that is in fact true; it is just that proving it means taking a detour through the infinite. Kirby and Paris said in their paper that this might be the first example of its kind from pure number theory; a little earlier, in 1977, Paris and Harrington had given an example from combinatorics.

$\omega$, ${\omega }^2$ and ${\epsilon }_0$ are all countable. Are there uncountable ordinals? Put all the countable ordinals together and call the result ${\omega }_1$. It is a well-ordered set, so it is an ordinal; it cannot be countable, or it would be one of its own elements, smaller than itself. So ${\omega }_1$ is the first uncountable ordinal, and its cardinality is written ${\aleph }_1$.

How “long” is ${\omega }_1$? Too long for the real line to hold:

So ${\aleph }_1$ is an “invisible” size: under the axiom of choice ${\aleph }_1\le 2^{{\aleph }_0}$, yet you cannot lay it out on the real line in order of size.

The alephs climb on and on: ${\aleph }_0,{\aleph }_1,{\aleph }_2,\dots ,{\aleph }_{\omega },\dots$, and every infinite cardinal (under the axiom of choice) is on this list. So where is the $\mathfrak{c}=2^{{\aleph }_0}$ from last lecture's three tiers? Is it ${\aleph }_1$?

This lecture did two things. First, we learned to “count” past infinity: well-ordering guarantees that “the next one” is always determined, ordinals are the lengths of well-orderings, and transfinite induction lets us walk past any limit. Second, we saw that this kind of infinity has a very concrete use: the Goodstein sequence climbs to astronomical numbers and then falls back to 0, and proving it takes only the sentence “ordinals cannot descend forever”; yet without a detour through the infinite, arithmetic cannot prove it.

Is $2^{{\aleph }_0}$ equal to ${\aleph }_1$? This is the continuum hypothesis, which Cantor conjectured in 1878 and Hilbert put first among his twenty-three problems in 1900. Next lecture we will see that the answer is neither “yes” nor “no.”

The number goes up, the shadow goes down;
and the shadow cannot go down forever.