Cantor–Schröder–Bernstein 定理

Cantor–Schröder–Bernstein 定理是集合论的基本结论, 指的是两个集合间若互相有单射, 则有双射.

直觉上说, 若有 $X$ 到 $Y$ 的单射, 就说明 $X$ 的大小不大于 $Y$ 的. 该定理表明若 $X$ 不大于 $Y$ 的同时 $Y$ 也不大于 $X$ 大, 那 $X$ 应该和 $Y$ 一样大.

Cantor–Schröder–Bernstein 定理也是集合的势的基本性质.

1陈述与承认选择公理的证明
2不依赖选择公理的证明
3历史
4相关概念

1陈述与承认选择公理的证明

定理 1.1 (Cantor–Schröder–Bernstein). 若对集合 $X, Y$ 存在单射 $f : X \to Y$ 与单射 $g : Y \to X$ , 则存在双射 $h : X \to Y$ .

若允许使用选择公理, 那么定理 1.1 无非是良序定理的直接推论, 下证之.

证明.

证明. 若 $X$ 或 $Y$ 为空集, 则结论显然正确, 下证二者均非空的情况.

由良序定理, 知存在唯一最小的序数 $∣ X ∣$ 使得映射 $ϕ : X \to \sim ∣ X ∣$ 是双射, 类似定义 $∣ Y ∣$ 和双射 $φ : Y \to \sim ∣ Y ∣$ .

易见映射 $φ \circ f : X \to ∣ Y ∣$ 是单射, 于是 $φ \circ f : X \to \sim im (φ \circ f) \subset ∣ Y ∣$ 是双射. 由良序定理, $im (φ \circ f)$ 也可以赋予良序, 记作 $α : im (φ \circ f) \to \sim ∣ im (φ \circ f) ∣$ . 于是有 $α \circ φ \circ f : X \to \sim ∣ im (φ \circ f) ∣ \leq ∣ Y ∣$ .

然而 $∣ X ∣$ 是能与 $X$ 建立双射的序数中最小者, 于是 $∣ X ∣ \leq ∣ im (φ \circ f) ∣ \leq ∣ Y ∣$ . 同理, $∣ Y ∣ \leq ∣ X ∣$ . 由序数的反称性, 可得 $∣ X ∣ = ∣ Y ∣$ .

于是

h := φ^{- 1} \circ ϕ : X \to \sim Y

即所求双射.

$□$

注 1.2. 上述证明中 $∣ X ∣, ∣ Y ∣$ 都是基数, 我们实际上证明了势的一个结论:

•	若存在单射 $f : X \to Y$ , 则 $∣ X ∣ \leq ∣ Y ∣$ .

2不依赖选择公理的证明

接下来介绍一种不使用选择公理的证法.

证明.

证明. 记 $X^{'} = X - g (Y)$ , 考虑 $X$ 的子集构成的集合 $F = {S \subset X ∣ X^{'} \cup h (S) \subset S}$ , 不难看出 $X \in F$ , 于是 $F$ 非空.

引理 2.1. 设集合 $A \in F$ , 则 $X^{'} \cup h (A) \in F$ .

引理的证明. 由于

h (A) \subset g (Y)

对任何

A \subset X

都成立, 于是

X^{'} \cap h (A) = \emptyset

. 欲证结论

X^{'} \cup h (X^{'} \cup h (A)) \subset X^{'} \cup h (A)

, 化为

h (X^{'} \cup h (A)) \subset h (A)

. 而

A \in F

, 由定义知

X^{'} \cup h (A) \subset A

, 两边作用

h

即得结论.

$■$

定义集合 $A_{0} := A \in F ⋂ A = {x \in X ∣ 对任意的 A \in F, 都有 x \in A},$ 下证 $A_{0} \in F$ . 由 $F$ 的定义, $\forall A \in F, X^{'} \subset A$ , 所以 $X^{'} \subset A_{0}$ . 只须证 $h (A_{0}) \subset A_{0}$ . 反设 $\exists x \in A_{0}$ 使得 $h (x) \in / A_{0}$ , 于是 $\exists A_{1} \in F$ 使得 $h (x) \in / A_{1}$ . 而由 $A_{0}$ 的定义有 $\forall A \in F, x \in A$ , 所以 $x \in A_{1}$ 且 $h (x) \in / A_{1}$ , 但这与 $A_{1} \in F$ 矛盾!

下证 $X^{'} \cup h (A_{0}) = A_{0}$ . 由引理 2.1, $X^{'} \cup h (A_{0}) \in F$ . 于是由 $A_{0}$ 的定义, $X^{'} \cup h (A_{0}) \supset A_{0}$ , 由 $F$ 的定义, $X^{'} \cup h (A_{0}) \subset A_{0}$ . 于是结论得证.

由于 $X^{'} \cap h (A_{0}) = \emptyset$ , 所以 $g \circ f (A_{0}) = h (A_{0}) = A_{0} - X^{'} = A_{0} - (X - g (Y)) = A_{0} \cap g (Y)$ . 于是 $f (A_{0}) = g^{- 1} (A_{0} \cap g (Y))$ .

记 $B_{0} = X - A_{0} = X - X^{'} \cup h (A_{0}) = X - ((X - g (Y)) \cup h (A_{0})) = g (Y) - h (A_{0})$ . 于是 $g^{- 1} (B_{0}) = g^{- 1} (g (Y) - h (A_{0}))$ .

由于 $(A_{0} \cap g (Y)) \cap B_{0} = \emptyset$ , 所以 $f (A_{0}) \cap g^{- 1} (B_{0}) = \emptyset$ . 同时因为 $(A_{0} - X^{'}) \cup B_{0} = g (Y)$ , 所以 $f (A_{0}) \cup g^{- 1} (B_{0}) = Y$ .

定义 $φ (x) := {f (x), g^{- 1} (x), 如果 x \in A_{0}; 如果 x \in B_{0} .$ 下证 $φ : X \to Y$ 即所求双射.

首先验证 $φ$ 确是映射. $B_{0}$ 是 $g$ 的像的子集, $g$ 又是单射, 于是 $g^{- 1} (x)$ 必是单点集.

下验证单性. $f (A_{0}) \cap g^{- 1} (B_{0}) = \emptyset$ 和 $f$ 单与 $g$ 是映射保证 $φ$ 单.

下验证满性.

f (A_{0}) \cup g^{- 1} (B_{0}) = Y

保证

φ

满.

$□$

3历史

Cantor 于 1887 年在论文 Mitteilungen zur Lehre vom Transfiniten (《关于超限数的注释》) 中首次提出该定理, 但没有给出证明.

同年,Dedekind 写出了一个证明, 但没有发表, 亦未告知 Cantor, 直至 1908 该证明才被 Zermelo 发现.

1896 年, Schröder 声称写出了一个 “证明”, 该 “证明” 于 1898 年发表但在 1902 年被 Korselt 发现是伪证.

Bernstein 则于 1897 年在 Cantor 参与的研讨会上发现了一个不依赖选择公理的证明, 该证明于 1898 年发表.

4相关概念

•	势
•	基数
•	Cantor 定理

术语翻译

Cantor–Schröder–Bernstein 定理 • 英文 Cantor–Schröder–Bernstein theorem • 德文 Satz von Cantor–Schröder–Bernstein • 法文 théorème de Cantor–Schröder–Bernstein

名字空间

视图

Cantor–Schröder–Bernstein 定理

1陈述与承认选择公理的证明

2不依赖选择公理的证明

3历史

4相关概念