康托爾-伯恩斯坦-施羅德定理

施羅德-伯恩斯坦定理（英語：Schröder–Bernstein theorem），又稱康托爾-伯恩斯坦-施羅德定理（Cantor-Bernstein-Schroeder theorem）是集合論中的一個基本定理，得名於康托爾、伯恩斯坦和施羅德。該定理陳述說：如果在集合 A 和 B 之間存在單射 f : A → B 和 g : B → A，則存在一個雙射 h : A → B。從勢的角度來看, 這意味着如果 |A| ≤ |B| 並且 |B| ≤ |A|，則 |A| = |B|，即A與B等勢。顯然，這是在基數排序中非常有用的特徵。

證明

下面是證明：

證明： 令

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

並令

$C=\bigcup _{n=0}^{\infty }C_{n}.$

對任意的 a∈A 定義映射

$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不在集合C₀中。因此由C₀的定義可知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)。由 C₀ 的定義知，a 不屬於 C₀。由於 f[C_n] 是 f[C]的一個子集，因而 b 不屬於任何一個 f[C_n]所以由集合C_n的遞歸定義以及g為單射（a 屬於g[f[C_n]]且a 屬於g[B]無法產生）的事實知，a = g(b) 不屬於 C_n+1= g[f[C_n]] 。因此，a 不屬於 C（C₀和C_n）那麼根據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。

注意這個 h 的定義是非構造性的，在這個意義下：不存在一般性方法在有限步驟內判定，對於任何給定集合 A 和 B 與單射 f 和 g，是否 A 的一個元素 x 不位於 C 中。對於特殊集合和映射這當然是可能的。

可視化

h 的定義可透過以下示意圖展示。

顯示的是部分的（不相交）集合 A 和 B ，以及映射 f 和 g的一部分。如果集合 A ∪ B，與兩個映射一起，被詮釋為一個有向圖，則這個雙向圖有多個連接起來的構件（component）。

這些可以分成四個類型：無限擴展到兩個方向的路徑，偶數長度的有限圈（環），開始於集合 A 中的無限路徑，和開始於集合 B 中的無限路徑（在圖中通過元素 a 的路徑是在兩個方向上無限的，所以這個圖包含每個類型的一個路徑）。一般的說，不可能在有限步驟內判定　A 或 B 的一個給定元素屬於那種類型的路徑。

上面定義的集合 C 恰好包含了那些開始在 A 中的無限路徑所經過的 A 的元素。映射 h 接着被按如下方式定義，對於所有路徑它生成一個雙射，把在路徑中 A 的每個元素，映射到在路徑中直接前於或後於它的 B 的一個元素。對於在兩個方向上都是無限的路徑，和對於有限圈，我們選擇映射所有元素到它在路徑中的前驅。

最初的證明

康托爾的早先證明有效的依賴於選擇公理，通過推導出良序定理的推論。上面給出的證明證實了可以證明這個結果而不使用選擇公理。

這個定理也叫做Schroeder-Bernstein定理，但一般會加上康托爾的名字，畢竟他貢獻了最初的版本。它也叫做Cantor-Bernstein定理。

引用

• Proofs from THE BOOK, p. 90. ISBN 3540404600