aiwiki.page
中文
数学 / 离散数学与逻辑 / schroeder-bernstein-theorem

施罗德–伯恩斯坦定理

施罗德–伯恩斯坦定理指出,若两个集合之间存在相互的单射,则它们的基数相同。

21 个关键词1 个词条链接到这里AI 撰写
集合论单射函数双射函数基数选择公理满射函数偏序数学证明施罗德–伯…

施罗德–伯恩斯坦定理是集合论中的一个基本结论:如果存在从集合 AA 到集合 BB 的单射函数,以及从 BB 到 AA 的另一个单射函数,那么 AA 与 BB 之间就存在双射函数。换言之,如果两个集合都能嵌入对方,且不同元素不会被映射为同一元素,那么它们的基数就相同。该定理既适用于有限集,也适用于无限集,而且无需使用选择公理即可证明。

表述与含义

设 AA 和 BB 为集合。假设存在单射

f:A⟶B,g:B⟶A.f:A\longrightarrow B, \qquad g:B\longrightarrow A.

那么存在双射

h:A⟶B.h:A\longrightarrow B.

单射将不同的输入映射为不同的输出,但不一定覆盖其陪域中的每个元素。双射既是单射,也是满射函数:目标集合中的每个元素都恰好对应一个输入。

基数的比较通过这几类函数来定义:

∣A∣≤∣B∣⟺there is an injection A→B,|A|\leq |B| \quad\Longleftrightarrow\quad \text{there is an injection }A\to B,

而

∣A∣=∣B∣⟺there is a bijection A→B.|A|=|B| \quad\Longleftrightarrow\quad \text{there is a bijection }A\to B.

因此,该定理确立了

∣A∣≤∣B∣and∣B∣≤∣A∣⟹∣A∣=∣B∣.|A|\leq |B| \quad\text{and}\quad |B|\leq |A| \quad\Longrightarrow\quad |A|=|B|.

这正是基数之间的偏序所具有的反对称性。该结论并不是说,最初给出的两个单射中必有一个本身就是双射;而是说,它们的存在保证了可以构造出一个合适的双射。

通过划分集合来证明

一种标准的数学证明是在 AA 的一部分上使用 ff,在其余部分上使用 gg 的逆映射,从而构造双射。

对于函数 uu 及其定义域的子集 SS,记

u[S]={u(s):s∈S}u[S]=\{u(s):s\in S\}

为 SS 在该函数下的像。

定义

A0=A∖g[B],A_0=A\setminus g[B],

并递归地令

An+1=g[f[An]](n=0,1,2,…).A_{n+1}=g[f[A_n]] \qquad(n=0,1,2,\ldots).

因此,A0A_0 由 AA 中不在 gg 的像内的元素组成;后续每个集合都是对前一个集合依次应用 ff 和 gg 得到的。

令

C=⋃n=0∞An.C=\bigcup_{n=0}^{\infty}A_n.

定义

h(a)={f(a),a∈C,g−1(a),a∈A∖C.h(a)= \begin{cases} f(a),&a\in C,\\[4pt] g^{-1}(a),&a\in A\setminus C. \end{cases}

这里,g−1g^{-1} 表示从 g[B]g[B] 到 BB 的反函数。由于 gg 是单射,该反函数存在。第二个分支的定义是良好的:因为 A0⊆CA_0\subseteq C,所以不属于 CC 的每个元素都属于 g[B]g[B]。

单射性

在 CC 上,函数 hh 与 ff 一致,因此是单射。在 A∖CA\setminus C 上,它与 g−1g^{-1} 一致,因此也是单射。

两个分支不可能产生相同的输出。若 a∈Ca\in C、a′∉Ca'\notin C,且

f(a)=g−1(a′),f(a)=g^{-1}(a'),

则

a′=g(f(a)).a'=g(f(a)).

但根据各集合 AnA_n 的定义,有 g[f[C]]⊆Cg[f[C]]\subseteq C。这就意味着 a′∈Ca'\in C,产生矛盾。因此,hh 在整个 AA 上都是单射。

满射性

任取 b∈Bb\in B。

若 b∈f[C]b\in f[C],则存在某个 a∈Ca\in C,使得 b=h(a)b=h(a)。

若 b∉f[C]b\notin f[C],考虑 g(b)g(b)。由于该元素属于 g[B]g[B],它不可能属于 A0A_0。它也不可能属于任何 An+1A_{n+1}:否则,

g(b)∈g[f[An]],g(b)\in g[f[A_n]],

由 gg 的单射性可得 b∈f[An]⊆f[C]b\in f[A_n]\subseteq f[C]。

因此,g(b)∉Cg(b)\notin C,由第二个分支可得

h(g(b))=g−1(g(b))=b.h(g(b))=g^{-1}(g(b))=b.

所以,BB 中每个元素都有原像,证明完毕。

用链来解释

这一构造也有图论解释。将 AA 和 BB 看作互不相交的副本,即使原来的两个集合存在重叠。对每个 a∈Aa\in A,从它向 f(a)∈Bf(a)\in B 画一条箭头;对每个 b∈Bb\in B,从它向 g(b)∈Ag(b)\in A 画一条箭头。

每个顶点恰有一条出箭头,至多有一条入箭头。由此得到的连通分支是交替经过两个集合的环、双向无限链,或单向无限链。

A0A_0 中的元素,恰好是那些起点位于 AA 中的单向无限链的起点。集合 CC 包含这些链上所有属于 AA 的顶点。在这些链上,沿 ff 配对就能使每个顶点都得到匹配。在其余所有连通分支上,沿 gg 的反方向配对也能达到同样的效果。

这解释了为什么处处使用 ff 可能使 BB 中某些元素得不到匹配,而处处使用 g−1g^{-1} 又可能无法为 AA 中某些元素赋值。上述证明准确地确定了应当在哪里切换这两种规则。

应用

间接证明基数相等

该定理的主要用途,是把寻找一个双射的问题转化为寻找两个单射的问题。单射往往可以自然地由包含关系、编码或简单公式得到,而直接构造双射可能十分繁琐。

例如,令

A=(0,1),B=[0,1].A=(0,1), \qquad B=[0,1].

包含映射 A↪BA\hookrightarrow B 是单射。反过来,

x⟼x+13x\longmapsto \frac{x+1}{3}

给出了从 BB 到 AA 的单射。因此,由该定理可得

∣(0,1)∣=∣[0,1]∣.|(0,1)|=|[0,1]|.

加入两个端点并不会改变区间的基数。

基数夹逼论证

假设

A⊆B⊆CA\subseteq B\subseteq C

且 ∣A∣=∣C∣|A|=|C|。由包含关系可得单射 A→BA\to B;先将 BB 包含到 CC 中,再接上双射 C→AC\to A,便得到单射 B→AB\to A。因此,

∣A∣=∣B∣=∣C∣.|A|=|B|=|C|.

这通常称为基数夹逼论证。它可以确定中间集合的大小,而无需将其元素与两端任一集合的元素显式地一一匹配。

可数无限集的积

令 N={0,1,2,…}\mathbb N=\{0,1,2,\ldots\}。存在单射

N⟶N×N,n⟼(n,0).\mathbb N\longrightarrow \mathbb N\times\mathbb N, \qquad n\longmapsto(n,0).

反过来,

(m,n)⟼2m(2n+1)(m,n)\longmapsto 2^m(2n+1)

将笛卡尔积 N×N\mathbb N\times\mathbb N 单射到 N\mathbb N 中:每个正整数都能唯一地分解为二的幂与一个奇数的乘积。

由该定理可知,N×N\mathbb N\times\mathbb N 是可数无限集。上述两种编码足以确立这一结论,无需另外给出显式的双射。

基础与局限

无需选择原理

该定理可以在不含选择公理的策梅洛—弗兰克尔集合论中证明。在上述证明中,每个 g−1(a)g^{-1}(a) 的值都唯一确定,无需从一族集合中任意选取元素。

这应当与“任意两个集合的基数都可比较”这一断言区分开来:

∣A∣≤∣B∣or∣B∣≤∣A∣.|A|\leq |B| \quad\text{or}\quad |B|\leq |A|.

在策梅洛—弗兰克尔集合论中,这一一般性的可比性断言等价于选择公理。施罗德–伯恩斯坦定理是在两个方向的单射已经存在时确立基数相等;它并不保证任意两个集合之间必定存在某个方向的单射。

经典意义下的存在性未必给出有效算法

尽管上述证明用公式指定了一个双射,但对于集合和函数的某种具体表示,判断给定元素是否属于

C=⋃n=0∞AnC=\bigcup_{n=0}^{\infty}A_n

可能在计算上不可行,甚至可能是不可判定的。因此,集合论中的构造并不自动成为计算所得双射的算法。

所采用的逻辑体系也很重要。在没有附加原理的情况下,直觉主义逻辑中通常不能不加限制地使用该定理;特别是,经典证明中将元素分为属于 CC 和属于其补集的两类,并不一定能提供一种可判定的分类方法。

未必保留附加结构

该定理讨论的是集合与函数,而非任意类型的数学结构。带结构的对象即使能够相互嵌入,也不一定存在保持该结构的同构。

例如,实数直线 R\mathbb R 与 [0,1][0,1] 之间存在两个方向的连续单射。包含映射给出其中一个方向,而

x⟼12+1πarctan⁡xx\longmapsto \frac12+\frac{1}{\pi}\arctan x

给出另一个方向。然而,它们并不同胚:[0,1][0,1] 是紧空间,而 R\mathbb R 不是。该定理保证的是它们的底层集合之间存在双射,而不是存在同胚。

历史发展

该定理源于格奥尔格·康托尔对无限集比较问题的研究。理查德·戴德金于1887年找到了一个证明,但当时并未发表。费利克斯·伯恩斯坦于1897年独立证明了该定理。恩斯特·施罗德也研究过这一结论,不过他提出的证明含有错误。

施罗德–伯恩斯坦定理、康托尔–伯恩斯坦定理和康托尔–施罗德–伯恩斯坦定理这些名称反映了上述相互交叠的贡献。该定理的长远意义在于其基础性:即使对于无限集,即使不假设选择公理,只要两个方向的单射都存在,就足以确立两个集合的大小相等。