确界原理 · 区间套

实数的完备性

有理数在数轴上稠密（见数轴与数系的四层嵌套 §3），却没有占满数轴：平方等于 $2$ 的那个位置上没有有理数（见无理数：反证、递降与超越）。「占满」这件事需要一条能写下来的性质，它就是完备性。

本页把完备性的四种常见说法摆在一起，说明它们讲的是同一件事，再给出这条性质在 $\mathbb{Q}$ 上失效的具体后果：二分法在有理数域内永不终止。

1 · 有上界却没有上确界的集合

考虑 $S = \{x \in \mathbb{Q} : x > 0,\ x^2 < 2\}$ 。它非空（ $1 \in S$ ），且有上界（ $2$ 是一个上界，因为 $x \ge 2$ 时 $x^2 \ge 4$ ）。有理数 $1$ 、 $1.4$ 、 $1.41$ 、 $1.414$ 都在 $S$ 里，它们的平方递增而始终小于 $2$ 。

图 1-1 · 以逐位加精的有限小数逼近

\sqrt 2

，每个近似都是有理数，平方递增而始终小于

2

。可逐步加精观察差距的收缩。

到第十项 $1.414213562$ 时平方是 $1.999999998945$ ，差距缩到十亿分之一量级，仍不为零。每一位取的都是下截断，所以这一列数永远停在 $S$ 内部，够不着那个平方恰为 $2$ 的位置。

反过来看 $S$ 的上界。 $2$ 是上界， $1.5$ 也是， $1.42$ 也是。有没有最小的那个？在 $\mathbb{Q}$ 内没有。

定理 1.1 设 $u$ 是正有理数且 $u^2 > 2$ ，则 $u' = (u + 2/u)/2$ 仍是有理数、仍满足 $u'^2 > 2$ ，且 $u' < u$ 。

证明 $u'$ 由 $u$ 经四则运算得到，故仍在 $\mathbb{Q}$ 内。直接计算得 $u'^2 - 2 = \left(\frac{u^2 - 2}{2u}\right)^2 > 0,$ 故 $u'^2 > 2$ 。又 $u - u' = (u^2 - 2)/(2u) > 0$ ，故 $u' < u$ 。∎

$S$ 的每个有理上界都能造出一个更小的有理上界，所以上界集合在 $\mathbb{Q}$ 内没有最小元， $S$ 在 $\mathbb{Q}$ 内没有上确界。

实跑 shrinkingBounds 从 $u = 2$ 出发，得到 $2 \to 3/2 \to 17/12 \to 577/408 \to 665857/470832$ ，超出量 $u^2 - 2$ 依次是 $2$ 、 $0.25$ 、 $6.94 \times 10^{-3}$ 、 $6.01 \times 10^{-6}$ 、 $4.51 \times 10^{-12}$ ：每步平方一次，收敛极快，但一次也没到零。代价写在分母上，这五项的分母位数是 $1, 1, 2, 3, 6$ ，再走两步到 $12$ 与 $25$ 。写完这段才注意到这串分数并不陌生——除首项外，它们就是 $\sqrt 2$ 的连分数渐近分数里第 $2^k$ 项（ $3/2$ 是第二项， $17/12$ 是第四项， $577/408$ 是第八项）。单测把这条对应关系钉住了，两条来路完全不同的算法给出同一批分数。

2 · 确界原理

定义 2.1（上确界） 集合 $A$ 的上确界 $\sup A$ 指 $A$ 的最小上界：它是 $A$ 的上界，且任何比它小的数都不是 $A$ 的上界。

定理 2.2（确界原理） 实数的每个有上界的非空子集都有上确界，且这个上确界是实数。

这条命题不是从别处推出来的，它是实数系的一条公理（或某种等价物）。 $\mathbb{Q}$ 不满足它：§1 的 $S$ 就是反例。把 $S$ 看成实数的子集，它的上确界存在，位置在 $\sqrt 2$ ；把 $S$ 看成有理数的子集，那个位置上没有有理数，上确界无处安放。

完备性这个词说的就是这件事： $\mathbb{R}$ 里没有「该有个数却没有数」的位置。

3 · 有理数域上失效的零点存在定理

完备性的后果里最容易看见的一条是零点存在定理：闭区间上连续且两端异号的函数必有零点（见函数的零点与二分法 §2）。这条定理的证明用到确界原理，因此它在 $\mathbb{Q}$ 上不成立。

$f(x) = x^2 - 2$ 就是反例。在有理数上考察它： $f(1) = -1 < 0$ ， $f(2) = 2 > 0$ ，两端异号； $f$ 在有理数上处处连续；而 $f(x) = 0$ 在 $\mathbb{Q}$ 内无解。定理的结论直接落空。

于是二分法在 $\mathbb{Q}$ 内不终止。每一步取中点、比较符号、丢掉一半，区间长度精确减半，端点始终是有理数，而中点的平方从不等于 $2$ 。

图 3-1 · 有理数域内对

x^2 = 2

的二分，每行是上一行的区间、涂色的是保留的一半，竖线标出目标位置。可切换目标并调二分次数；目标换成

x^2 = 4

时二分当场命中。

实跑 bisectOnQ 走到第 $64$ 步：区间宽 $1/2^{63} \approx 1.08 \times 10^{-19}$ ，中点的分母已是 $20$ 位十进制数，符号判定从未给出零。跑到第 $120$ 步仍是如此——单测就断言到这一步。对照组把目标换成 $4$ ，起始区间取 $[1, 3]$ ，第二步的中点就是 $2$ ，二分当场终止。差别不在算法，在根是不是有理数。

另有一处容易说错的地方。区间在缩小，但每个区间里的有理数一直是无穷多个（稠密性并没有失效）。失效的是这一列区间的公共部分：在 $\mathbb{R}$ 内它是单点 $\{\sqrt 2\}$ ，在 $\mathbb{Q}$ 内它是空集。区间套定理断言的正是这个交集非空，而 $\mathbb{Q}$ 上它落空了。

4 · 完备性的等价表述

同一条性质有若干种常见写法，互相之间可以循环推导，任取一条当公理，其余都成为定理。

完备性的四种表述，以及各自在 ℚ 上失效时给出的反例。
表述	内容	在 $\mathbb{Q}$ 上的反例
确界原理	有上界的非空集合有上确界	$S = \{x \in \mathbb{Q} : x > 0,\ x^2 < 2\}$
单调有界定理	单调递增且有上界的数列收敛	$1, 1.4, 1.41, 1.414, \dots$
区间套定理	长度趋于零的闭区间套交于唯一一点	§3 的二分区间列
Cauchy 列收敛	任何 Cauchy 列都有极限	同上，二分的两个端点列

四条在 $\mathbb{Q}$ 上同时失效，而且反例都能由 $\sqrt 2$ 这一个位置造出来。这不是巧合：缺一个位置就足以让四条一起断掉，而补上全部这样的位置就得到 $\mathbb{R}$ 。

警示 · 「单调有界必收敛」在 $\mathbb{Q}$ 上失效，靠的不是数列本身有问题。 $1, 1.4, 1.41, \dots$ 每一项都是有理数、单调递增、有上界 $2$ ，作为有理数列它完全合法，只是极限不在 $\mathbb{Q}$ 里。判断收敛必须先说清「在哪个集合里收敛」，省掉这个限定词就会得出矛盾的结论。

5 · 实数的两种构造

上面把完备性当作公理来用。若要从 $\mathbb{Q}$ 出发把 $\mathbb{R}$ 造出来，有两条经典路线，都在 19 世纪后期给出。

Dedekind 分割把每个实数定义为 $\mathbb{Q}$ 的一个切分：取 $\mathbb{Q}$ 的子集 $A$ ，要求它非空、不等于 $\mathbb{Q}$ 、对向下封闭（ $x \in A$ 且 $y < x$ 则 $y \in A$ ）、且无最大元，那条切口就是一个实数。前两条不可省，否则 $\emptyset$ 与 $\mathbb{Q}$ 自身也会各算一个实数，凭空多出两个端点。 $\sqrt 2$ 对应的切口是 §1 的 $S$ 与它的补。Cantor 与 Méray 的路线用 Cauchy 列：把有理 Cauchy 列按「差趋于零」分类，每个等价类是一个实数， $1, 1.4, 1.41, \dots$ 所在的那一类就是 $\sqrt 2$ 。

两条构造给出同构的结果，本页不展开验证。值得记的是它们的共同点：都是拿 $\mathbb{Q}$ 里的无穷多个对象打包成 $\mathbb{R}$ 里的一个数。这一点在代码里有直接的回响——机器存不下无穷多个对象，所以计算机里的「实数」只能是别的东西，见浮点数：实数在代码里的残影。

6 · 参考文献

Completeness of the real numbers. Wikipedia. 完备性的各种等价表述及它们的互推。https://en.wikipedia.org/wiki/Completeness_of_the_real_numbers
Least-upper-bound property. Wikipedia. 确界原理，以及有理数为何不具备它。https://en.wikipedia.org/wiki/Least-upper-bound_property
Dedekind cut. Wikipedia. 用分割构造实数。https://en.wikipedia.org/wiki/Dedekind_cut
Construction of the real numbers. Wikipedia. Cauchy 列等价类构造与两条路线的等价性。https://en.wikipedia.org/wiki/Construction_of_the_real_numbers
Nested interval theorem. Wikipedia. 区间套定理的陈述与它同确界原理的关系。https://en.wikipedia.org/wiki/Nested_intervals