Contents 5 sections
  1. 一个「显然」的结论
  2. 先看一个例子
  3. 证明:把元素串成链
  4. 应用:∣R∣=∣P(N)∣|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|
  5. 再往前走

一个「显然」的结论

对有限集合,若 ∣A∣≤∣B∣|A| \le |B| 且 ∣B∣≤∣A∣|B| \le |A|,那么 ∣A∣=∣B∣|A| = |B|,这是不言而喻的。上一篇我们用「存在单射」定义了无穷集合的 ≤\le,同样的结论是否还成立?

定理 1(Schröder–Bernstein)

若存在单射 f:A→Bf : A \to B 和单射 g:B→Ag : B \to A,则存在双射 h:A→Bh : A \to B。

困难在于:ff 和 gg 都可能「不满」,ff 漏掉 BB 的一部分,gg 漏掉 AA 的一部分。我们需要从两个都不完美的映射里,拼出一个完美的一一对应。

这个定理有一段曲折的历史:Cantor 叙述过它但没有证明;Dedekind 在 1887 年给出了证明,却没有发表;Schröder 在 1896 年前后给出的证明有漏洞;1897 年,19 岁的 Felix Bernstein 给出了正确的证明。

先看一个例子

A=[0,1]A = [0,1],B=[0,1)B = [0,1)。单射很容易找:

  • f:[0,1]→[0,1)f : [0,1] \to [0,1),f(x)=x/2f(x) = x/2;
  • g:[0,1)→[0,1]g : [0,1) \to [0,1],g(y)=yg(y) = y。

但直接写出一个双射就没那么显然了,因为端点 11 必须找个地方安放。一个办法是让 1,12,14,18,…1, \tfrac12, \tfrac14, \tfrac18, \dots 整体「挪一格」:

h(x)={x/2若 x=2−k, k=0,1,2,…x其他情况.h(x) = \begin{cases} x/2 & \text{若 } x = 2^{-k},\ k = 0, 1, 2, \dots \\ x & \text{其他情况.} \end{cases}

这个 hh 是双射:11 被送到 12\tfrac12,12\tfrac12 被送到 14\tfrac14,依此类推,像希尔伯特旅馆一样,这条链上的每个元素都往后挪一格,于是 11 有了去处,其他点原地不动。下面的一般证明,本质上就是在系统地寻找这些需要挪动的「链」。

证明:把元素串成链

不妨设 AA 与 BB 不相交(否则给元素加上标签区分)。对任意元素,我们沿着映射往回追溯它的祖先:

  • a∈Aa \in A 的「父亲」是满足 g(b)=ag(b) = a 的 b∈Bb \in B(若存在;因为 gg 是单射,至多一个);
  • b∈Bb \in B 的「父亲」是满足 f(a)=bf(a) = b 的 a∈Aa \in A(若存在,同样至多一个)。

从一个元素出发不断找父亲,只会出现三种结局:

  1. 追溯到某个 AA 中没有父亲的元素后停止,称该元素「起源于 AA」;
  2. 追溯到某个 BB 中没有父亲的元素后停止,称它「起源于 BB」;
  3. 永远追溯不完(无穷长的祖先链,或者绕回自身形成环),称它「无始」。

据此把 AA 分成三部分 AA,AB,A∞A_A, A_B, A_\infty,把 BB 分成 BA,BB,B∞B_A, B_B, B_\infty。

引理 2

ff 把 AAA_A 双射到 BAB_A,把 A∞A_\infty 双射到 B∞B_\infty;gg 把 BBB_B 双射到 ABA_B。

证明.

元素 xx 与 f(x)f(x) 有相同的祖先链(f(x)f(x) 的父亲就是 xx),所以 ff 保持起源:f(AA)⊆BAf(A_A) \subseteq B_A,f(A∞)⊆B∞f(A_\infty) \subseteq B_\infty,同理 g(BB)⊆ABg(B_B) \subseteq A_B。

只需再说明满射。取 b∈BAb \in B_A:它起源于 AA,所以 bb 本身不是起点,一定有父亲 aa,满足 f(a)=bf(a) = b,且 aa 同样起源于 AA,即 a∈AAa \in A_A。B∞B_\infty 中的元素也一定有父亲(否则它自己就是起点),父亲同属 A∞A_\infty。ABA_B 中的元素同理一定有 BBB_B 中的父亲。单射性由 f,gf, g 的单射性直接得到。

∎
定理的证明.

定义

h(x)={f(x)x∈AA∪A∞,g−1(x)x∈AB.h(x) = \begin{cases} f(x) & x \in A_A \cup A_\infty, \\ g^{-1}(x) & x \in A_B. \end{cases}

由 引理 2,hh 分别把 AAA_A、A∞A_\infty、ABA_B 双射到 BAB_A、B∞B_\infty、BBB_B,三块互不相交且拼成整个 BB,所以 hh 是双射。

∎

注意这个证明里没有用到选择公理,也没有用到任何关于 AA、BB 的具体结构,只用到了「单射的逆至多一个」这一点。对 A∞A_\infty 也可以改用 g−1g^{-1},同样成立,所以双射一般不唯一。

应用:∣R∣=∣P(N)∣|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|

有了这个定理,比较两个集合的大小只需要两个方向各找一个单射,不必直接构造双射。

推论 3

实数集与正整数集的幂集等势:∣R∣=∣P(N)∣|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|。

证明.

因为 x↦1πarctan⁡x+12x \mapsto \tfrac{1}{\pi}\arctan x + \tfrac12 是 R\mathbb{R} 到 (0,1)(0,1) 的双射,只需比较 (0,1)(0,1) 与 P(N)\mathcal{P}(\mathbb{N})。

(0,1)→P(N)(0,1) \to \mathcal{P}(\mathbb{N}) 的单射:把 xx 写成不以无穷个 1 结尾的二进制小数 0.b1b2b3⋯0.b_1 b_2 b_3\cdots(这样的写法唯一),令 x↦{ n:bn=1 }x \mapsto \{\, n : b_n = 1 \,\}。不同的 xx 有不同的二进制展开,所以是单射。

P(N)→(0,1)\mathcal{P}(\mathbb{N}) \to (0,1) 的单射:子集 SS 对应十进制小数 0.c1c2c3⋯0.c_1 c_2 c_3\cdots,其中 n∈Sn \in S 时 cn=3c_n = 3,否则 cn=5c_n = 5。这些小数不含 0 和 9,写法唯一,所以不同子集对应不同的数,而且都落在 (0,1)(0,1) 内。

由 定理 1,两者等势。

∎

结合上一篇的 Cantor 定理,我们终于得到严格的结论:∣N∣<∣P(N)∣=∣R∣|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| = |\mathbb{R}|。

再往前走

  • 用同样的方法可以证明 ∣R2∣=∣R∣|\mathbb{R}^2| = |\mathbb{R}|:平面上的点和直线上的点一样多。Cantor 在 1877 年发现这一点时,在给 Dedekind 的信里写道:「我看到了,但我不相信。」
  • 定理的结论 ∣A∣≤∣B∣,∣B∣≤∣A∣⇒∣A∣=∣B∣|A| \le |B|, |B| \le |A| \Rightarrow |A| = |B| 说明「≤\le」是一个真正的偏序;而「任意两个集合都可以比较大小」则需要选择公理才能证明。