Cantor–Bernstein-Schröder 定理及其证明简介
1 定理简介
Cantor–Bernstein-Schröder 定理，也称作 Schröder–Bernstein 定理、Cantor–Bernstein 定理，是集合论中的重要定理。它的内容十分简单：如果集合 \(A\) 到集合 \(B\) 存在单射，且集合 \(B\) 到集合 \(A\) 存在单射，则集合 \(A\) 与集合 \(B\) 之间存在双射。它也可以等价地描述成：设 \(\alpha\) 和 \(\beta\) 是两个奇数，且 \(a \le b \and \beta \le a\)，则 \(\alpha = \beta\)。
这个定理的证明有许多种 [1]，这篇论文将覆盖其中一种，但是我们会用两种形式表述它，然后简单论述为什么这两个证明本质是相同的。
笔者在初学这个定理时误以为它很自然，甚至在做其他问题的证明时没有对这个问题加以考证就直接使用了这个定理，但只是在有限集下这个定理很显然。在集合的势达到无穷时，集合基数的定义、比较、运算都是十分复杂的问题。这个定理在在对无限集的势的比较中起到了关键的作用，是集合论中的重要定理之一。
2 历史背景
这个定理当中出现了三位数学家的名字，他们都来自德国。他们分别是 Georg Cantor (1845~1918)、Felix Bernstein (1878~1956) 和 Ernst Schröder (1841~1902)。
Georg Cantor 在 1887 年发表了这一定理，但并没有给出证明。
在 1887 年 7 月 11 日，Richard Dedekind（就是发明了 Dedekind 分割定义实数系的数学家）证明了这一定理。他的证明基于他的 chain theory，而不是 ZFC 公理体系中的 axiom of choice（选择公理）。但是，Dedekind 并没有发表自己的证明，也没有把自己的证明告知 Cantor。他是第一位发表证明（也是正确的证明）的数学家，但是并没有出现在定理的名称中。
1895 年 Cantor 发表了这一定理的证明。他认为，这个定理是良序定理的推论，但是他当时并没有证明良序定理。良序定理在 1915 年被证明和选择公理（也就是 ZFC 公理体系中的 C, Axiom of Choice）等价。
1897 年，19 岁的 Bernstein 实现了证明，他是著名数学家高斯的学生。他的证明不依赖于选择公理；几乎同时地，Schröder 也实现了证明。但是，Schröder 的证明在 1902 年被发现是错误的。
1897 年，Dedekind 再次证明了这个定理。
1898 年，Bernstein 和 Schröder 分别发表了自己的证明。
这四位科学家都对这个定理的提出或证明做出了卓越的贡献。
3 第一种表述
这个证明采用了构造“交叉”形式的双射的方法，思路十分巧妙，而且证明非常简洁。
记 \(A_0 = A, B_0 = B\)。由两个集合互相构成单射，有\(\varphi: A_0 \rightarrow B_1 \subset B_0, \psi: B_0 \rightarrow A_1 \subset A_0\) 是两个双射。
我们归纳地定义
\[\begin{aligned} B_1 = \varphi(A_0)&, A_1 = \psi(B_0)\\ B_2 = \varphi(A_1)&, A_2 = \psi(B_1)\\ &\vdots\\ B_n = \varphi(A_{n - 1})&, A_n = \psi(B_{n - 1})\\ &\vdots \end{aligned} \]Lemma 1: \(A_0 \supset A_1 \supset \cdots \supset A_n \supset \cdots, B_0 \supset B_1 \supset \cdots \supset B_n \supset \cdots\)
证明：\(\forall i \in \mathbb N^+\)，由于 \(B_i \subset B_{i - 1}\) 且 \(A_i = \psi(B_{i - 1}), A_{i + 1} = \psi(B_i)\)
且 \(\psi\) 为双射，那么 \(A_i\) 中元素与 \(B_{i - 1}\) 中元素一一对应，\(A_{i + 1}\) 中元素与 \(B_i\) 中元素一一对应。
结合 \(B_i \subset B_{i - 1}\)，那么与 \(B_i\) 对应的集合必定属于与 \(B_{i - 1}\) 对应的集合，即 \(A_{i + 1}\subset A_i\)，又 \(A_1 \subset A_0\)，则 \(A_0 \supset A_1 \supset \cdots \supset A_n \supset \cdots\) 成立。
同理可证 \(B_0 \supset B_1 \supset \cdots \supset B_n \supset \cdots\)。
**Lemma 2: **记 \(f\vert_A\) 表示将映射 \(f\) 的原像限定在集合 \(A\) 内，\(\forall n \in \mathbb N, \varphi\vert_{A_n\setminus A_{n + 1}}: A_n\setminus A_{n + 1}\rightarrow B_{n + 1}\setminus B_{n + 2}\) 和 \(\psi\vert_{B_n\setminus B_{n+1}}:B_n\setminus B_{n+1}\to A_{n+1}\setminus A_{n+2}\) 都是双射。
证明：由于 \(\forall n \in \mathbb N, \varphi\vert_{A_n}\) 为双射，\(\varphi\vert_{A_{n + 1}}\) 为双射，由 \(A_n\) 与 \(\varphi(A_n)\)，\(B_n\) 与 \(\psi(B_n)\) 的双射关系可知 \(A_n\setminus A_{n + 1}\) 中各元素与 \(\varphi(A_n)\setminus \varphi(A_{n + 1})\) 中元素一一对应，也即\(A_n\setminus A_{n + 1}\) 中各元素与 \(B_{n + 1}\setminus B_{n + 2}\) 中元素一一对应，\(B_n\setminus B_{n + 1}\) 与 \(A_{n + 1}\setminus A_{n + 2}\) 同理。则 lemma 2 成立。
**Lemma 3: **
\[A_0 = (\bigcup_{n = 0}^{+\infty}(A_{2n}\setminus A_{2n + 1}))\cup (\bigcup_{n = 0}^{+\infty}(A_{2n + 1}\setminus A_{2n + 2}))\cup (\bigcap_{n = 0}^{+\infty}A_n)\\ B_0 = (\bigcup_{n = 0}^{+\infty}(B_{2n}\setminus B_{2n + 1}))\cup (\bigcup_{n = 0}^{+\infty}(B_{2n + 1}\setminus B_{2n + 2}))\cup (\bigcap_{n = 0}^{+\infty}B_n) \]且等号右方的各项两两不相交。
证明：我们详细叙述 \(A_0\) 的证明，\(B_0\) 同理。
\(A_0 = (A_0\setminus A_1) \cup A_1\)，而 \(A_1 = (A_1\setminus A_2)\cup A_2, \cdots\)
我们可以得到 \(A_{2n} = (A_{2n} \setminus A_{2n + 1})\cup (A_{2n + 1} \setminus A_{2n + 2}) \cup A_{2n + 2}\) 并递归地进行下去，由于 \(A_{i}\setminus A_{i + 1}\) 与 \(A_{i + 1}\) 无交集，那么 \(A_{i}\setminus A_{i + 1}\) 与 \(A_{i + 1}\setminus A_{i + 2}\) 无交集。
没有进入过 \(A_i \setminus A_{i + 1}\) 的元素 \(x\) 恰好满足 \(\forall n \in \mathbb N, x \in A_n\)，即 \(x \in \bigcap_{n = 0}^{+\infty}A_n\)（这是充要的）。
所以上式成立，并且各项之间不交。
**Lemma 4: **
\[\varphi\big|_{\bigcup_{n=0}^{+\infty} (A_{2n}\backslash A_{2n+1}) }: \bigcup_{n=0}^{+\infty} (A_{2n}\backslash A_{2n+1}) \to \bigcup_{n=0}^{+\infty} (B_{2n+1}\backslash B_{2n+2})\\ \psi\big|_{\bigcup_{n=0}^{+\infty} (B_{2n}\backslash B_{2n+1}) }: \bigcup_{n=0}^{+\infty} (B_{2n}\backslash B_{2n+1}) \to \bigcup_{n=0}^{+\infty} (A_{2n+1}\backslash A_{2n+2})\\ \psi\big|_{\bigcap_{n=0}^{+\infty}B_n}:\bigcap_{n=0}^{+\infty}B_n\to \bigcap_{n=0}^{+\infty}A_n \]这三个映射都是双射。
证明：
由 lemma 2 可知，\(\varphi\vert_{A_n\setminus A_{n + 1}}: A_n\setminus A_{n + 1}\rightarrow B_{n + 1}\setminus B_{n + 2}\) 是双射。又由于 \(\bigcup_{n=0}^{\infty} (A_{2n}\setminus A_{2n+1})\) 各项不交，并且 \(\varphi\vert_{A_0}\) 是双射，因此 \(\bigcup_{n=0}^{\infty} (A_{2n}\setminus A_{2n+1})\) 各项的值域必不相交。
我们合并 \(\varphi\vert_{A_0 \setminus A_1}, \varphi\vert_{A_2\setminus A_3}, \ldots\) 的定义域和值域得到双射 \(\varphi\big|_{\bigcup_{n=0}^{\infty} (A_{2n}\setminus A_{2n+1}) }\)。
\(\psi\big|_{\bigcup_{n=0}^{\infty} (B_{2n}\setminus B_{2n+1}) }\) 同理。
而 \(\psi\big|_{\bigcap_{n=0}^{\infty}B_n}\) 的定义域则是被 \(B_n\setminus B_{n + 1}\) 都排除在外的元素构成的集合，它的值域是被 \(\psi(B_n \setminus B_{n + 1}) = A_{n + 1}\setminus A_{n + 2}\) 都排除在外的集合，也就是 \(\bigcap_{n = 0}^{+\infty} A_n\)。\(\varphi\) 定义在 \(\bigcup_{n = 0}^{+\infty}B_n \setminus B_{n + 1}\) 的部分是双射，则我们排除掉这些部分（及它们的像）之后的部分依然满足一一对应关系，是双射。
Lemma 5:
\[\theta(x) = \begin{cases} \varphi(x), & {\rm if} x \in \bigcup_{n=0}^{+\infty} (A_{2n}\setminus A_{2n+1})\\ \psi^{-1}(x), & {\rm if } x\in \left( \bigcup_{n=0}^{+\infty} (A_{2n+1}\setminus A_{2n+2})\right) \cup \left( \bigcap_{n=0}^{+\infty} A_n\right) \end{cases} \]是 \(A\) 到 \(B\)（\(A_0\) 到 \(B_0\)）的双射。
首先，由 lemma 3，\(\theta(x)\) 的定义域恰好为 \(A_0\)，且两种情况不相交。
我们已经证明 \(\varphi(x)\) 的部分为双射，值域为 \(\bigcup_{n=0}^{+\infty} (B_{2n+ 1}\setminus B_{2n+2})\)。
\(\psi^{-1}(x)\) 的部分也是双射，值域 \(\bigcup_{n=0}^{+\infty} (B_{2n}\setminus B_{2n+1})\cup (\bigcup_{n = 0}^{+\infty}B_n)\)。
由于两部分分别为双射，值域互不相交，且值域的并恰为 \(B_0\)（由 lemma 3）。
则 \(\theta(x)\) 为 \(A\rightarrow B\) 的双射。
Q.E.D.
图解证明：
其中红色的箭头表示 \(\varphi\)，蓝色的箭头表示 \(\psi\)。
总结：这个证明的核心就是拆分 \(A\) 和 \(B\)，使得 \(A\) 和 \(B\) 的各部分之间构造出双射。
我们刚入手这个问题时，最棘手的部分就是 \(B_0\setminus B_1\) 上的元素没有 \(\varphi^{-1}\) 与之对应，\(A_0\setminus A_1\) 同理，所以我们只能将 \(B_0\setminus B_1\) 中元素通过 \(\psi\) 来与 \(A\) 对应。这种证明从这样的思想出发，递归地构造了 \(A_n, B_n\)，构造出“交叉”形式的双射 \(\theta\)，十分具有创造性，并且证明过程比较简洁。
4 第二种表述
这种证明的核心是构造多条由映射关系连接成的“链”，使得每个元素恰好在一条链上。它的表述更直观。
同样记 \(A\) 到 \(B\) 的单射，也就是 \(A\) 到 \(B\) 的子集的双射为 \(\varphi\)，\(B\) 到 \(A\) 的单射为 \(\psi\)。
记元素 \(x\in A\) 所在的的“链”为 \(x, \varphi(x), \psi(\varphi(x)), \varphi(\psi(\varphi(x))), \ldots\)，以及沿着 \(\varphi, \psi\) 向原像的方向所能到达的元素 \(\psi^{-1}(x), \varphi^{-1}(\psi^{-1}(x)), \psi^{-1}(\varphi^{-1}(\psi^{-1}(x))), \ldots\)（如果存在的话）。对于 \(\forall y \in B\) 同理。
每一个元素都恰好属于一条链。
由于 \(\varphi, \psi\) 都是单射，所以只要有一个元素的像是 \(x\)，那么 \(\varphi^{-1}(x)\) 存在且唯一。对于 \(y \in B\) 同理。
这样的链一定属于一下四类之一：
- 这个链构成了一个环
- 这个链在反方向（沿着反函数的方向）可以走无穷多步，并且元素没有重复。
- 从 \(A\) 中的元素起始：这个链的起始元素 \(x \in A\) 并没有 \(\psi(y) = x\) 与之对应，而从这个元素向 \(\varphi(x), \psi(\varphi(x)), \ldots\) 的方向行进，经过的每一个元素都有一个原像与之对应。
- 从 \(B\) 中的元素起始：这个链的起始元素 \(y \in B\) 并没有 \(\varphi(x) = y\) 与之对应，而从这个元素向 \(\psi(y), \varphi(\psi(y)), \ldots\) 的方向行进，经过的每一个元素都有一个原像与之对应。
现在我们构造 \(\theta\)。
如果 \(x\in A\) 在第一、二、三类链中，则 \(\theta(x) = \varphi(x)\)。
如果 \(x \in A\) 在第四类链中，则 \(\theta(x) = \psi^{-1}(x)\)。
下面我们证明相应的 \(\varphi(x)\) 与 \(\psi^{-1}(x)\) 都存在，且 \(\theta\) 是单射，也是满射。
Part 1:
由四种链的定义，任取链上一个属于 \(A\) 的元素 \(x_0\)，\(\varphi(x_0)\) 一定有定义。
对于第四类链，这条链的起始元素是 \(B\) 中的，也就是说这条链上 \(A\) 中的元素都可以沿着 \(\psi\) 向上回溯到 \(B\) 中元素，也就是 \(\psi^{-1}(x)\) 存在。
Part 2:
也就是说只要 \(\theta(x_1) = \theta(x_2)\)，就有 \(x_1 = x_2\)。
注意到 \(\theta(x)\) 总是与 \(x\) 在一条链上，因此 \(x_1, x_2\) 一定在一条链上。
-
这条链是第一、二、三类链：\(\theta(x_1) = \varphi(x_1), \theta(x_2) = \varphi(x_2)\)
由于 \(\varphi\) 是单射，则 \(\theta(x_1) = \theta(x_2)\Rightarrow \varphi(x_1) = \varphi(x_2)\Rightarrow x_1 = x_2\)
-
这条链是第四类链：
记 \(\theta(x_1) = \theta(x_2) = y\)，则 \(\psi(y) = x_1, \psi(y) = x_2\)，由于 \(\psi\) 是一个映射，那么 \(x_1 = x_2\) 显然成立。
Part 3:
\(\forall y \in B\)，我们要找到对应的 \(x \in A\) 使得 \(\theta(x) = y\)。
由于 \(y\) 在恰好一条链上，我们考虑其所在链的类型，如果是第一、二、三类，那么由定义，这类链上所有的 \(y'\in B\) 都能找到 \(x' \in A,\ {\rm s. t. }\ \varphi(x') = y'\)。
由于 \(x', y'\) 在同一条链上，那么 \(\theta(x') = \varphi(x') = y\)。
如果是第四类链，那么这类链上所有的 \(y' \in B\) 都有 \(x'\in A,\ {\rm s.t.}\ \psi(y') = x'\)。
那么 \(\theta(x') = \psi^{-1}(x') = y'\)。得证。
Q.E.D.
总结：
这个证明中我们构造出一条条链，并且运用每一个点都在恰好一条链上这个性质，更方便地进行分类讨论。
为什么说两种证明本质是相同的？我们可以证明第一类链和第二类链上的所有点都属于 \(\bigcap_{n = 0}^{+\infty}A_n\) 或 \(\bigcap_{n = 0}^{+\infty}B_n\)，且第三类、第四类链上的点属于一个 \(A_{m - 1}\setminus A_m\) 或 \(B_{m - 1}\setminus B_m\)：
对于第一、二类链上 \(A\) 中的点，假设它属于 \(A_{m - 1} \setminus A_{m}\)，则它沿着原像的方向走 \(m - 1\) 步以后一定会到达 \(A_0\setminus A_1\) 或 \(B_0 \setminus B_1\)（视 \(m\) 的奇偶性讨论），而根据 \(A_0 \setminus A_1 (B_0\setminus B_1)\) 的定义，它不属于 \(\psi\)（或 \(\varphi\)）的值域，因此不能再向上回溯。而第一类、第四类点均可以向上回溯无穷多步，故矛盾。对于 \(B\) 中的点同理。
对于这些点，我们规定 \(\theta(x) = \varphi(x)\) 或 \(\psi^{-1}(x)\) 其实都是成立的，都能构成双射。
而对于第三、四类链上 \(A\) 中的点，向前回溯有限步都会停止，相当于走到 \(A_0 \setminus A_1\) 或 \(B_0\setminus B_1\)，那么我们就必须分类讨论。第三类链从 \(A_0\setminus A_1\) 中的元素起始，行经的所有元素属于 \(A_{2n}\setminus A_{2n + 1}\) 或 \(B_{2n + 1}\setminus B_{2n + 2}\)，而第四类链从 \(B_0\setminus B_1\) 中的元素起始，行经的所有元素属于 \(B_{2n}\setminus B_{2n + 1}\) 或 \(A_{2n +1}\setminus A_{2n + 2}\)，刚好对应第一类证明中的两种情况。
这个证明来自 Julius König。
5 应用
我们可以利用这个定理证明 \([0, 1]\) 与 \([0, 1)\) 是等势的。
\[f:[0, 1]\rightarrow [0, 1)\\ f(x) = \frac x 2;\\ g:[0, 1)\rightarrow [0, 1]\\ g(x) = x. \]我们再应用 Cantor-Bernstein-Schröder 定理，就可以证明 \([0, 1]\) 与 \([0, 1)\) 是等势的。
运用上述证明的第一种表述，我们可以构造出 \(\theta(x)\)。
我们注意到
\[\begin{aligned} A_0 = [0, 1]&, B_0 = [0, 1)\\ A_1 = [0, 1)&, B_1 = [0, \dfrac 1 2]\\ A_2 = [0, \dfrac 1 2]&, B_2 = [0, \dfrac 1 2)\\ A_3 = [0, \dfrac 1 2)&, B_3 = [0, \dfrac 1 4]\\ &\vdots \end{aligned} \]容易证明 \(A_{2n}\setminus A_{2n + 1} = \{\dfrac{1}{2^n}\}\)。
则
\[\theta(x) = \begin{cases} \dfrac 1 2 x&, x = \dfrac 1 {2^n}, n \in \mathbb N\\ x&, {\rm otherwise} \end{cases} \]这就是我们常见的构造方式。
6 总结
这个定理的证明有许多种，还有 Dedekind, Bernstein, Zermelo 的等等 [1]。但是上述证明是比较直观的，并且不需要用到许多集合论中的公理。
这个定理为无限集势的比较奠定了基础，其证明也极大方便了“用两个相互的单射构造出双射”这一过程。许多集合论的初学者也借此理解了为什么非负偶数集合和自然数集合等势、为什么整数集和自然数集等势等等问题。总而言之，Cantor-Bernstein-Schröder 定理对于集合论是十分基础且重要的。
参考资料
历史资料主要来源于维基百科：https://en.wikipedia.org/wiki/Schröder–Bernstein_theorem
[1] 英国皇家学会的报告：https://royalsocietypublishing.org/doi/10.1098/rsta.2018.0031
第一种表述：https://www.uio.no/studier/emner/matnat/math/MAT4640/v14/4640-suplement.pdf
第二种表述同样参考于维基百科。
标签：infty,psi,Schr,der,varphi,证明,setminus,Cantor,2n From： https://www.cnblogs.com/gznpp/p/17331142.html