《CantorBernsteinSchroeder.docVIP

康托尔-伯恩斯坦-施罗德(Cantor-Bernstein-Schroeder)定理 是集合论中的一个基本定理。该定理陈述说: 如果在集合 A 和 B 之间存在单射 f?: A → B 和 g?: B → A，则存在一个双射 h?: A → B.依据这两个集合的势, 这意味着如果 |A| ≤ |B| 并且 |B| ≤ |A|，则 |A| = |B|, 即A与B等势. 显然, 这是在基数排序中非常有用的特征. 证明: 令 并令 则对任意的 a∈A 定义映射 如果a不在集合C中, 那么a不在集合C0中. 因此由C0的定义可知a?∈?g[B]. 由于g是单射, 他的逆映射g?–1(a)存在. 接下来验证 h?:?A?→?B 就是想要的双射. 满射: 对任何 b?∈?B. 如果 b?∈?f[C], 那么存在 a?∈?C 使得 b?=?f(a). 因此由h的定义可知 b?=?h(a) . 如果 b 不属于 f[C], 定义 a?=?g(b). 由 C0 的定义知, a 不属于 C0. 由于 f[Cn] 是 f[C]的一个子集, 因而 b 不属于任何一个 f[Cn], 所以由集合Cn的递归定义知, a?=?g(b) 不属于 Cn+1?= g[f[Cn]]. 因此, a 不属于 C. 那么根据h的定义 b?= g?–1(a)?= h(a) . 单射: 若h(a)=h(b),则有a∈C∧b∈C,a?C∧b?C,a∈C∧b?C,a?C∧b∈C四种情况，对于前两种情况，由f与g?–1是单射得a=b，对于第三种情况，有f(a)=g?–1(b)?g(f(a))=g(g?–1(b))?g°f(a)=b,又由前提a∈C，而C在g°f下封闭，于是b∈C，但是由前提得b?C，矛盾了，因此第三种情况不可能出现，同理第四种情况也不可能出现，这说明ran(f|C)∩ran(g?–1|A\C)=?。综上若h(a)=h(b)，一定有a=b。 在日常交流中，基数或量数是对应量词的“数”，例如在以下句子中的“一”及“四”：“有一个橙，有四个柑”。序数是对应排列的“数”，例如在以下句子中的“（第）一”及“（第）二”：“这人一不会打字，二不懂速记，所以不可以做秘书”；“第二个人正在进来”。 在数学上，基数或势，即集合中包含的元素的“个数”（背景知识：势的比较），是日常交流中基数的概念在数学上的精确化（并使之不再受限于有限情形）。有限集合的基数，其意义与日常用语中的“基数”相同（见上段），例如 {a, b, c} 的基数是 3。无限集合的基数，其意义在于比较两个集的大小，例如整数集和分数集的基数相同，是以它们是一样大；整数集的基数比实数集的小；是以后者是比较大的集合。 历史 Aleph-0, 最小的无限基数 康托尔在1874年～1884年引入最原始的集合论（现称朴素集合论）时, 首次引入基数概念。 他最先考虑的是集合 {1,2,3} 和 {2,3,4}，它们并非相同，但有相同的基数。骤眼看来，这是显而易见，但究竟可谓两个集合有相同数目的元素？ 康托尔的答案，是所谓一一对应，即把两个集合的元素一对一的排起来——若能做到，两个集合的基数自然相同。这答案，容易理解但却是革命性的，因为用相同的方法即可比较任意集合，包括无穷集合的大小。 最先被考虑的无穷集合是自然数集 N = {1, 2, 3, ...} 及其无限子集。他把所有与 N 能一一对应的集为可数集。大出康托尔意外，原来 N 的所有无限子集都能与 N一一对应。他把 N 的基数称为，是最少的艾礼富数。 康托尔发现，原来有理数集合与代数数集合也是可数的。于是乎在1874年初，他尝试证明是否所有无限集合均是可数，稍后他得出著名的对角论证法，实数集是不可数的。实数集的基数，记作c，代表连续统。 接着康托尔构作一个比一个大的集合，得出一个比一个大的基数，而这些巨大集合的元素已不可如实数般书写出来。因此关于基数的一般理论，需要一个新的语言描述，这就是康托尔发明集合论的主因。 康托尔随后提出连续统假设： c 就是第二个超穷数 , 即継 之后最小的基数。多年后，数学家发现这假设是不能证明的，即接受或否定它会得出两套不同但逻辑上可行的公理化集合论。 动机 在非形式使用中，基数就是通常被称为计数的东西。它们同一于开始于 0 的自然数(就是 0, 1, 2, ...)。计数严格的是可形式定义为有限基数的东西。无限基数只出现在高级数学和逻辑中。 更加形式的说，非零数可以用于两个目的: 描述一个集合的大小，或描述一个元素在序列中位置。对于有限集合和序列，可以轻易的看出着两个概念是相符的，因为对于所有描述在序列中的一个位置的数，我们可以构造一个有精确的正好大小的集合，比如 3 描述 c 在序列 a,b,c,d,... 中的位置，并且