施罗德–伯恩斯坦定理是集合论中的一个基本结论:如果存在从集合 A 到集合 B 的单射函数,以及从 B 到 A 的另一个单射函数,那么 A 与 B 之间就存在双射函数。换言之,如果两个集合都能嵌入对方,且不同元素不会被映射为同一元素,那么它们的基数就相同。该定理既适用于有限集,也适用于无限集,而且无需使用选择公理即可证明。
表述与含义
设 A 和 B 为集合。假设存在单射
f:A⟶B,g:B⟶A.
那么存在双射
h:A⟶B.
单射将不同的输入映射为不同的输出,但不一定覆盖其陪域中的每个元素。双射既是单射,也是满射函数:目标集合中的每个元素都恰好对应一个输入。
基数的比较通过这几类函数来定义:
∣A∣≤∣B∣⟺there is an injection A→B,
而
∣A∣=∣B∣⟺there is a bijection A→B.
因此,该定理确立了
∣A∣≤∣B∣and∣B∣≤∣A∣⟹∣A∣=∣B∣.
这正是基数之间的偏序所具有的反对称性。该结论并不是说,最初给出的两个单射中必有一个本身就是双射;而是说,它们的存在保证了可以构造出一个合适的双射。
通过划分集合来证明
一种标准的数学证明是在 A 的一部分上使用 f,在其余部分上使用 g 的逆映射,从而构造双射。
对于函数 u 及其定义域的子集 S,记
u[S]={u(s):s∈S}
为 S 在该函数下的像。
定义
A0=A∖g[B],
并递归地令
An+1=g[f[An]](n=0,1,2,…).
因此,A0 由 A 中不在 g 的像内的元素组成;后续每个集合都是对前一个集合依次应用 f 和 g 得到的。
令
C=n=0⋃∞An.
定义
h(a)={f(a),g−1(a),a∈C,a∈A∖C.
这里,g−1 表示从 g[B] 到 B 的反函数。由于 g 是单射,该反函数存在。第二个分支的定义是良好的:因为 A0⊆C,所以不属于 C 的每个元素都属于 g[B]。
单射性
在 C 上,函数 h 与 f 一致,因此是单射。在 A∖C 上,它与 g−1 一致,因此也是单射。
两个分支不可能产生相同的输出。若 a∈C、a′∈/C,且
f(a)=g−1(a′),
则
a′=g(f(a)).
但根据各集合 An 的定义,有 g[f[C]]⊆C。这就意味着 a′∈C,产生矛盾。因此,h 在整个 A 上都是单射。
满射性
任取 b∈B。
若 b∈f[C],则存在某个 a∈C,使得 b=h(a)。
若 b∈/f[C],考虑 g(b)。由于该元素属于 g[B],它不可能属于 A0。它也不可能属于任何 An+1:否则,
g(b)∈g[f[An]],
由 g 的单射性可得 b∈f[An]⊆f[C]。
因此,g(b)∈/C,由第二个分支可得
h(g(b))=g−1(g(b))=b.
所以,B 中每个元素都有原像,证明完毕。
用链来解释
这一构造也有图论解释。将 A 和 B 看作互不相交的副本,即使原来的两个集合存在重叠。对每个 a∈A,从它向 f(a)∈B 画一条箭头;对每个 b∈B,从它向 g(b)∈A 画一条箭头。
每个顶点恰有一条出箭头,至多有一条入箭头。由此得到的连通分支是交替经过两个集合的环、双向无限链,或单向无限链。
A0 中的元素,恰好是那些起点位于 A 中的单向无限链的起点。集合 C 包含这些链上所有属于 A 的顶点。在这些链上,沿 f 配对就能使每个顶点都得到匹配。在其余所有连通分支上,沿 g 的反方向配对也能达到同样的效果。
这解释了为什么处处使用 f 可能使 B 中某些元素得不到匹配,而处处使用 g−1 又可能无法为 A 中某些元素赋值。上述证明准确地确定了应当在哪里切换这两种规则。
应用
间接证明基数相等
该定理的主要用途,是把寻找一个双射的问题转化为寻找两个单射的问题。单射往往可以自然地由包含关系、编码或简单公式得到,而直接构造双射可能十分繁琐。
例如,令
A=(0,1),B=[0,1].
包含映射 A↪B 是单射。反过来,
x⟼3x+1
给出了从 B 到 A 的单射。因此,由该定理可得
∣(0,1)∣=∣[0,1]∣.
加入两个端点并不会改变区间的基数。
基数夹逼论证
假设
A⊆B⊆C
且 ∣A∣=∣C∣。由包含关系可得单射 A→B;先将 B 包含到 C 中,再接上双射 C→A,便得到单射 B→A。因此,
∣A∣=∣B∣=∣C∣.
这通常称为基数夹逼论证。它可以确定中间集合的大小,而无需将其元素与两端任一集合的元素显式地一一匹配。
可数无限集的积
令 N={0,1,2,…}。存在单射
N⟶N×N,n⟼(n,0).
反过来,
(m,n)⟼2m(2n+1)
将笛卡尔积 N×N 单射到 N 中:每个正整数都能唯一地分解为二的幂与一个奇数的乘积。
由该定理可知,N×N 是可数无限集。上述两种编码足以确立这一结论,无需另外给出显式的双射。
基础与局限
无需选择原理
该定理可以在不含选择公理的策梅洛—弗兰克尔集合论中证明。在上述证明中,每个 g−1(a) 的值都唯一确定,无需从一族集合中任意选取元素。
这应当与“任意两个集合的基数都可比较”这一断言区分开来:
∣A∣≤∣B∣or∣B∣≤∣A∣.
在策梅洛—弗兰克尔集合论中,这一一般性的可比性断言等价于选择公理。施罗德–伯恩斯坦定理是在两个方向的单射已经存在时确立基数相等;它并不保证任意两个集合之间必定存在某个方向的单射。
经典意义下的存在性未必给出有效算法
尽管上述证明用公式指定了一个双射,但对于集合和函数的某种具体表示,判断给定元素是否属于
C=n=0⋃∞An
可能在计算上不可行,甚至可能是不可判定的。因此,集合论中的构造并不自动成为计算所得双射的算法。
所采用的逻辑体系也很重要。在没有附加原理的情况下,直觉主义逻辑中通常不能不加限制地使用该定理;特别是,经典证明中将元素分为属于 C 和属于其补集的两类,并不一定能提供一种可判定的分类方法。
未必保留附加结构
该定理讨论的是集合与函数,而非任意类型的数学结构。带结构的对象即使能够相互嵌入,也不一定存在保持该结构的同构。
例如,实数直线 R 与 [0,1] 之间存在两个方向的连续单射。包含映射给出其中一个方向,而
x⟼21+π1arctanx
给出另一个方向。然而,它们并不同胚:[0,1] 是紧空间,而 R 不是。该定理保证的是它们的底层集合之间存在双射,而不是存在同胚。
历史发展
该定理源于格奥尔格·康托尔对无限集比较问题的研究。理查德·戴德金于1887年找到了一个证明,但当时并未发表。费利克斯·伯恩斯坦于1897年独立证明了该定理。恩斯特·施罗德也研究过这一结论,不过他提出的证明含有错误。
施罗德–伯恩斯坦定理、康托尔–伯恩斯坦定理和康托尔–施罗德–伯恩斯坦定理这些名称反映了上述相互交叠的贡献。该定理的长远意义在于其基础性:即使对于无限集,即使不假设选择公理,只要两个方向的单射都存在,就足以确立两个集合的大小相等。