要证明集合 $[0, 1] imes [0, 1]$(即单位正方形)与集合 $[0, 1]$ 等势,我们需要找到一个双射(一一对应)函数 $f: [0, 1] imes [0, 1] o [0, 1]$。
这听起来有点匪夷所思,因为一个二维的区域怎么可能和一条线段上的点一一对应呢?但集合论的威力就在于它允许我们进行这种看似不可能的对应。
核心思想:将二维空间“编码”到一维空间
我们需要一种方法,能够把一个有序对 $(x, y)$(其中 $x, y in [0, 1]$)唯一地映射到一个实数 $z in [0, 1]$,并且这个映射是可逆的。
一种常用的、直观的方法是利用小数展开。
具体构造方法:Cantor Pairing Function 的推广
坎特配对函数(Cantor Pairing Function)可以用来给自然数对建立一一对应,我们可以借鉴这个思想,但需要处理实数。
假设我们有一个点 $(x, y) in [0, 1] imes [0, 1]$。我们可以将 $x$ 和 $y$ 分别写成它们的十进制小数展开:
$x = 0.a_1 a_2 a_3 dots = sum_{i=1}^{infty} frac{a_i}{10^i}$
$y = 0.b_1 b_2 b_3 dots = sum_{i=1}^{infty} frac{b_i}{10^i}$
其中 $a_i, b_i in {0, 1, 2, dots, 9}$ 是十进制的数字。
一个关键的挑战:小数表示的唯一性问题
我们需要注意,有些实数存在两种十进制表示。例如,$0.5$ 可以写成 $0.5000dots$ 或者 $0.4999dots$。如果我们在构造函数时处理不好这一点,可能会导致函数不是单射(一对多)。
为了解决这个问题,我们约定使用不以无限多个9结尾的小数表示。例如,我们选择 $0.5$ 而不是 $0.4999dots$。这样,任何实数在 $[0, 1]$ 内都有唯一的有限或无限不循环小数表示,或者说,所有以无限多个9结尾的表示都被排除(例如,我们使用 $0.5$ 而不是 $0.4999dots$;我们使用 $1.0$ 而不是 $0.9999dots$)。
构造函数 $f$
现在,我们可以利用 $x$ 和 $y$ 的小数位来构造一个实数 $z in [0, 1]$。一种自然的想法是“交织”它们的数字:
$z = 0.a_1 b_1 a_2 b_2 a_3 b_3 dots = frac{a_1}{10} + frac{b_1}{100} + frac{a_2}{1000} + frac{b_2}{10000} + frac{a_3}{100000} + frac{b_3}{1000000} + dots$
更一般地,这个函数可以写成:
$f(x, y) = sum_{i=1}^{infty} left( frac{a_i}{10^{2i1}} + frac{b_i}{10^{2i}}
ight)$
证明 $f$ 是双射
我们需要证明这个函数 $f$ 是单射(一对一)和满射(映上)。
1. 单射性 (Injectivity)
假设我们有两个不同的点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 在 $[0, 1] imes [0, 1]$ 中。我们要证明 $f(x_1, y_1)
eq f(x_2, y_2)$。
如果 $(x_1, y_1)
eq (x_2, y_2)$,那么要么 $x_1
eq x_2$,要么 $y_1
eq y_2$(或者两者都不同)。
情况 1: $x_1
eq x_2$
根据我们关于小数表示的约定(不以无限个9结尾),如果 $x_1
eq x_2$,那么它们的十进制展开至少有一个数字位是不同的。假设第一个不同的数字位是 $a_k$ 和 $a'_k$(对应于 $x_1$ 和 $x_2$)。
在构造的 $f$ 中,这个差异会体现在 $10^{2k1}$ 的位置上(来自 $x$ 的第 $k$ 位小数)。例如,如果 $x_1 = 0.123dots$ 和 $x_2 = 0.124dots$,那么 $a_1 = a'_1$, $a_2 = a'_2$, $a_3
eq a'_3$。在 $f(x_1, y_1)$ 中,这个差异会出现在 $0.1010dots$ 的位置,而在 $f(x_2, y_2)$ 中,它会出现在 $0.1040dots$ 的位置。
情况 2: $y_1
eq y_2$
同理,如果 $y_1
eq y_2$,那么它们的十进制展开至少有一个数字位是不同的。假设第一个不同的数字位是 $b_k$ 和 $b'_k$(对应于 $y_1$ 和 $y_2$)。
在构造的 $f$ 中,这个差异会体现在 $10^{2k}$ 的位置上(来自 $y$ 的第 $k$ 位小数)。例如,如果 $y_1 = 0.567dots$ 和 $y_2 = 0.568dots$,那么 $b_1 = b'_1$, $b_2 = b'_2$, $b_3
eq b'_3$。在 $f(x_1, y_1)$ 中,这个差异会出现在 $0.00500dots$ 的位置,而在 $f(x_2, y_2)$ 中,它会出现在 $0.00800dots$ 的位置。
由于我们交织的数字是按照 $a_1, b_1, a_2, b_2, dots$ 的顺序排列的,一个 $x$ 的不同会在一个奇数位($10^{2i1}$)产生差异,一个 $y$ 的不同会在一个偶数位($10^{2i}$)产生差异。这保证了只要 $(x_1, y_1)
eq (x_2, y_2)$,它们的交织表示就会不同,从而 $f(x_1, y_1)
eq f(x_2, y_2)$。
关键在于避免无限多个9的歧义:如果我们允许无限多个9,例如 $0.5 = 0.4999dots$,那么 $(0.5, 0.0) o 0.5000dots$ 和 $(0.4999dots, 0.0) o 0.409090dots$ 的映射就可能出现问题。但一旦我们固定了小数表示(比如,从不使用无限多个9结尾),比如 $x_1 = 0.5$ (表示为 $0.5000dots$) 而 $x_2 = 0.4999dots$ (我们不使用这种表示),那么它们的交织就会不同。如果 $x_1=0.5$ ($0.5000dots$) and $x_2=0.49$ ($0.4900dots$) then $(0.5, 0.0) o 0.500000dots$ and $(0.49, 0.0) o 0.409000dots$ which are different.
如果我们选择 $(x_1, y_1) = (0.5, 0.0)$ 并且 $(x_2, y_2) = (0.4999dots, 0.0)$。如果我们坚持使用不含无限个9的表示,那么 $x_1 = 0.5000dots$, $y_1 = 0.0000dots$。而 $x_2$ 就不允许用 $0.4999dots$ 来表示,它应该被表示为 $0.5000dots$。所以如果 $(x_1, y_1)
eq (x_2, y_2)$,那么它们的数字序列 $(a_1, b_1, a_2, b_2, dots)$ 和 $(a'_1, b'_1, a'_2, b'_2, dots)$ 中至少有一个对应位置上的数字是不同的。由于小数表示唯一(排除无限9),这个不同的位置决定了 $f(x_1, y_1)$ 和 $f(x_2, y_2)$ 的不同。
2. 满射性 (Surjectivity)
现在我们需要证明对于 $[0, 1]$ 中的任意一个实数 $z$,都存在一个点 $(x, y) in [0, 1] imes [0, 1]$ 使得 $f(x, y) = z$。
设 $z in [0, 1]$。我们可以将 $z$ 写成它的十进制小数展开:
$z = 0.c_1 c_2 c_3 c_4 c_5 c_6 dots = sum_{j=1}^{infty} frac{c_j}{10^j}$
同样,我们排除以无限多个9结尾的表示。
我们可以从 $z$ 的小数位中“提取”出数字来构建 $x$ 和 $y$。我们将 $z$ 的小数位交错地分配给 $x$ 和 $y$:
令 $x = 0.a_1 a_2 a_3 dots$
令 $y = 0.b_1 b_2 b_3 dots$
将 $z$ 的小数位按顺序分配:
$a_1 = c_1$, $b_1 = c_2$
$a_2 = c_3$, $b_2 = c_4$
$a_3 = c_5$, $b_3 = c_6$
$dots$
一般地,对于 $i ge 1$:
$a_i = c_{2i1}$
$b_i = c_{2i}$
这样我们就构造了一个有序对 $(x, y) = (0.c_1 c_3 c_5 dots, 0.c_2 c_4 c_6 dots)$。
关键问题:这个构造是否保证 $x, y in [0, 1]$?
是的,因为我们是从 $z in [0, 1]$ 的小数位中提取的数字,所以构造出的 $x$ 和 $y$ 的小数位都在 ${0, 1, dots, 9}$ 之间,因此 $x$ 和 $y$ 自然就属于 $[0, 1]$。
关键问题:构造的 $x$ 和 $y$ 是否有无限多个9的问题?
我们构造 $x$ 和 $y$ 的方法是直接从 $z$ 的小数位中选取。如果 $z$ 本身没有无限多个9结尾,那么我们直接提取的小数位也不会导致 $x$ 或 $y$ 出现无限多个9的问题。
例如,如果 $z = 0.121212dots$,那么 $c_1=1, c_2=2, c_3=1, c_4=2, dots$。
$x = 0.1111dots = 0.1$ (我们选择不含无限9的表示)
$y = 0.2222dots = 0.2$ (我们选择不含无限9的表示)
然后 $f(0.1, 0.2) = 0.121212dots = z$。
如果 $z$ 有无限多个9结尾,例如 $z = 0.129999dots = 0.13$。
我们约定使用 $z = 0.130000dots$。
那么 $c_1=1, c_2=3, c_3=0, c_4=0, dots$。
$x = 0.1000dots = 0.1$
$y = 0.3000dots = 0.3$
$f(0.1, 0.3) = 0.130000dots = z$。
这个构造方式确保了 $x$ 和 $y$ 的小数表示是有效的(不含无限个9),并且它们的值都在 $[0, 1]$ 中。
通过交织这些数字,我们重新得到了 $z$:
$f(x, y) = 0.a_1 b_1 a_2 b_2 a_3 b_3 dots = 0.c_1 c_2 c_3 c_4 c_5 c_6 dots = z$
总结一下证明过程
1. 定义函数: 构造了一个将单位正方形的点 $(x, y)$ 映射到单位实数线段上的点 $z$ 的函数 $f$,该函数通过交织 $x$ 和 $y$ 的十进制小数位来实现。
$x = 0.a_1 a_2 a_3 dots$
$y = 0.b_1 b_2 b_3 dots$
$f(x, y) = 0.a_1 b_1 a_2 b_2 a_3 b_3 dots$
为了确保函数的唯一性和可逆性,我们约定所有涉及实数的小数表示都避免使用无限个9结尾的形式。
2. 证明单射性: 假设两个不同的点 $(x_1, y_1)
eq (x_2, y_2)$。由于它们不同,它们的十进制表示必然至少在某一位上不同。通过交织小数位的方法,这些不同会体现在最终生成的实数 $f(x_1, y_1)$ 和 $f(x_2, y_2)$ 的小数点后的不同位置上,从而确保 $f(x_1, y_1)
eq f(x_2, y_2)$。
3. 证明满射性: 对于 $[0, 1]$ 中的任意一个实数 $z$,将其写成十进制小数表示(避免无限个9)。然后从 $z$ 的小数位中提取奇数位置的数字构造 $x$,偶数位置的数字构造 $y$。这样构造的 $x$ 和 $y$ 都在 $[0, 1]$ 中,并且通过 $f$ 函数的交织操作,恰好能还原出 $z$。
结论
由于我们找到了一个从 $[0, 1] imes [0, 1]$ 到 $[0, 1]$ 的双射函数 $f$,因此这两个集合是等势的。这意味着单位正方形上的点的数量与单位实数线段上的点的数量是相同的,都属于“连续统的基数”,记作 $mathfrak{c}$ 或 $2^{aleph_0}$。
这个证明也展示了集合论中一个令人惊讶但重要的结果:一个维度比另一个维度高的空间,在集合势的意义下,可能与低维度空间具有相同的“点数”。这是通过一种巧妙的“空间填充”曲线的思想来实现的,尽管这里的函数 $f$ 本身并不是一条连续的空间填充曲线(它在某些点上存在不连续性,如果从拓扑角度看)。但从集合论的角度看,它成功地建立了双射关系。