Contents 5 sections
- 一个「显然」的结论
- 先看一个例子
- 证明:把元素串成链
- 应用:∣R∣=∣P(N)∣
- 再往前走
一个「显然」的结论
对有限集合,若 ∣A∣≤∣B∣ 且 ∣B∣≤∣A∣,那么 ∣A∣=∣B∣,这是不言而喻的。上一篇我们用「存在单射」定义了无穷集合的 ≤,同样的结论是否还成立?
定理 1(Schröder–Bernstein)若存在单射 f:A→B 和单射 g:B→A,则存在双射 h:A→B。
困难在于:f 和 g 都可能「不满」,f 漏掉 B 的一部分,g 漏掉 A 的一部分。我们需要从两个都不完美的映射里,拼出一个完美的一一对应。
这个定理有一段曲折的历史:Cantor 叙述过它但没有证明;Dedekind 在 1887 年给出了证明,却没有发表;Schröder 在 1896 年前后给出的证明有漏洞;1897 年,19 岁的 Felix Bernstein 给出了正确的证明。
先看一个例子
A=[0,1],B=[0,1)。单射很容易找:
- f:[0,1]→[0,1),f(x)=x/2;
- g:[0,1)→[0,1],g(y)=y。
但直接写出一个双射就没那么显然了,因为端点 1 必须找个地方安放。一个办法是让 1,21,41,81,… 整体「挪一格」:
h(x)={x/2x若 x=2−k, k=0,1,2,…其他情况.
这个 h 是双射:1 被送到 21,21 被送到 41,依此类推,像希尔伯特旅馆一样,这条链上的每个元素都往后挪一格,于是 1 有了去处,其他点原地不动。下面的一般证明,本质上就是在系统地寻找这些需要挪动的「链」。
证明:把元素串成链
不妨设 A 与 B 不相交(否则给元素加上标签区分)。对任意元素,我们沿着映射往回追溯它的祖先:
- a∈A 的「父亲」是满足 g(b)=a 的 b∈B(若存在;因为 g 是单射,至多一个);
- b∈B 的「父亲」是满足 f(a)=b 的 a∈A(若存在,同样至多一个)。
从一个元素出发不断找父亲,只会出现三种结局:
- 追溯到某个 A 中没有父亲的元素后停止,称该元素「起源于 A」;
- 追溯到某个 B 中没有父亲的元素后停止,称它「起源于 B」;
- 永远追溯不完(无穷长的祖先链,或者绕回自身形成环),称它「无始」。
据此把 A 分成三部分 AA,AB,A∞,把 B 分成 BA,BB,B∞。
引理 2f 把 AA 双射到 BA,把 A∞ 双射到 B∞;g 把 BB 双射到 AB。
证明.元素 x 与 f(x) 有相同的祖先链(f(x) 的父亲就是 x),所以 f 保持起源:f(AA)⊆BA,f(A∞)⊆B∞,同理 g(BB)⊆AB。
只需再说明满射。取 b∈BA:它起源于 A,所以 b 本身不是起点,一定有父亲 a,满足 f(a)=b,且 a 同样起源于 A,即 a∈AA。B∞ 中的元素也一定有父亲(否则它自己就是起点),父亲同属 A∞。AB 中的元素同理一定有 BB 中的父亲。单射性由 f,g 的单射性直接得到。
∎
定理的证明.定义
h(x)={f(x)g−1(x)x∈AA∪A∞,x∈AB.由 引理 2,h 分别把 AA、A∞、AB 双射到 BA、B∞、BB,三块互不相交且拼成整个 B,所以 h 是双射。
∎
注意这个证明里没有用到选择公理,也没有用到任何关于 A、B 的具体结构,只用到了「单射的逆至多一个」这一点。对 A∞ 也可以改用 g−1,同样成立,所以双射一般不唯一。
应用:∣R∣=∣P(N)∣
有了这个定理,比较两个集合的大小只需要两个方向各找一个单射,不必直接构造双射。
推论 3实数集与正整数集的幂集等势:∣R∣=∣P(N)∣。
证明.因为 x↦π1arctanx+21 是 R 到 (0,1) 的双射,只需比较 (0,1) 与 P(N)。
(0,1)→P(N) 的单射:把 x 写成不以无穷个 1 结尾的二进制小数 0.b1b2b3⋯(这样的写法唯一),令 x↦{n:bn=1}。不同的 x 有不同的二进制展开,所以是单射。
P(N)→(0,1) 的单射:子集 S 对应十进制小数 0.c1c2c3⋯,其中 n∈S 时 cn=3,否则 cn=5。这些小数不含 0 和 9,写法唯一,所以不同子集对应不同的数,而且都落在 (0,1) 内。
由 定理 1,两者等势。
∎
结合上一篇的 Cantor 定理,我们终于得到严格的结论:∣N∣<∣P(N)∣=∣R∣。
再往前走
- 用同样的方法可以证明 ∣R2∣=∣R∣:平面上的点和直线上的点一样多。Cantor 在 1877 年发现这一点时,在给 Dedekind 的信里写道:「我看到了,但我不相信。」
- 定理的结论 ∣A∣≤∣B∣,∣B∣≤∣A∣⇒∣A∣=∣B∣ 说明「≤」是一个真正的偏序;而「任意两个集合都可以比较大小」则需要选择公理才能证明。