康托尔-伯恩斯坦-施罗德定理

维基百科,自由的百科全书
跳转至: 导航搜索

康托尔-伯恩斯坦-施罗德(Cantor-Bernstein-Schroeder)定理集合论中的一个基本定理。该定理陈述说: 如果在集合 AB 之间存在单射 f : ABg : BA,则存在一个双射 h : AB.依据这两个集合的, 这意味着如果 |A| ≤ |B| 并且 |B| ≤ |A|,则 |A| = |B|, 即AB等势. 显然, 这是在基数排序中非常有用的特征.

证明[编辑]

下面是证明:

证明:

C_0=A\setminus g[B],\qquad C_{n+1}=g[f[C_n]]\quad \forall n\ge 0

并令

C=\bigcup_{n=0}^\infty C_n.

则对任意的 aA 定义映射


h(a)=\left\{
\begin{matrix}
f(a) & \,\,\mbox{if }a\in C \\
g^{-1}(a) & \mbox{if }a\not\in C
\end{matrix}
\right.

如果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),则有aCbC,aCbC,aCbC,aCbC四种情况,对于前两种情况,由fg –1是单射得a=b,对于第三种情况,有f(a)=g –1(b)⇒g(f(a))=g(g –1(b))⇒g°f(a)=b,又由前提aC,而Cg°f下封闭,于是bC,但是由前提得bC,矛盾了,因此第三种情况不可能出现,同理第四种情况也不可能出现,这说明ran(f|C)∩ran(g –1|A\C)=∅。综上若h(a)=h(b),一定有a=b



注意这个 h 的定义是非构造性的,在不存在一般性方法在有限步骤内判定,对于任何给定集合 AB 与单射 fg,是否 A 的一个元素 x 不位于 C 中的意义上。对于特殊集合和映射这当然是可能的。

可视化[编辑]

h 的定义可可视化为如下示意图。

example of the definition of h

显示的是部分的(不相交)集合 AB 和在一起的部分的映射 fg.如果集合 AB,与两个映射一起,被解释为一个有向图,则这个双向图有多个连接起来的构件(component)。

这些可以分成四个类型: 无限扩展到两个方向的路径,偶数长度的有限圈(环),开始于集合 A 中的无限路径,和开始于集合 B 中的无限路径(在图中通过元素 a 的路径是在两个方向上无限的,所以这个图包含所有类型的一个路径)。一般的说,不可能在有限步骤内判定 AB 的一个给定元素属于那种类型的路径。

上面定义的集合 C 精确的包含是开始在 A 中的无限路径的一部分的 A 的元素。映射 h 接着被按如下方式定义,对于所有路径它生成一个双射,映射在路径中 A 的每个元素到在路径中直接前于或后于它 B 的一个元素。对于在两个方向上都是无限的路径,和对于有限圈,我们选择映射所有元素到它在路径中的前驱。

最初的证明[编辑]

康托尔的早先证明有效的依赖于选择公理,通过推导出良序定理的推论。上面给出的证明证实了可以证明这个结果而不使用选择公理。

这个定理也叫做 Schroeder-Bernstein 定理,但是更加倾向于加上康托尔的名字,毕竟他贡献了最初的版本。它也叫做 Cantor-Bernstein 定理

引用[编辑]