基本介紹
- 中文名：康托爾-伯恩施坦定理
- 外文名：Cantor-Bernstein theorem
- 領域：集合論
簡介,證明,可視化,最初的證明,
簡介
康托爾-伯恩斯坦定理（Cantor-Bernstein theorem）是集合論中的一個基本定理，得名於康托爾、伯恩斯坦和 Ernst Schröder。該定理陳述說：如果在集合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(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(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是單射得a=b。對於第三種情況，有f(a)=g(b)⇒g(f(a))=g(g(b))⇒g°f(a)=b，又由前提a∈C，而C在g°f下封閉，於是b∈C，但是由前提得b∉C，矛盾了，因此第三種情況不可能出現。同理第四種情況也不可能出現，這說明ran(f|C) ∩ ran(g|A\C) = ∅。綜上若h(a)=h(b)，一定有a=b。
注意這個h的定義是非構造性的，在這個意義下：不存在一般性方法在有限步驟內判定，對於任何給定集合A和B與單射f和g，是否A的一個元素x不位於C中。對於特殊集合和映射這當然是可能的。
可視化
h的定義可透過右圖展示。
圖1.h的定義
圖1.h的定義顯示的是部分的（不相交）集合A和B，以及映射f和g的一部分。如果集合A∪B，與兩個映射一起，被詮釋為一個有向圖，則這個雙向圖有多個連線起來的構件（component）。
這些可以分成四個類型：無限擴展到兩個方向的路徑，偶數長度的有限圈（環），開始於集合A中的無限路徑，和開始於集合B中的無限路徑（在圖中通過元素a的路徑是在兩個方向上無限的，所以這個圖包含每個類型的一個路徑）。一般的說，不可能在有限步驟內判定A或B的一個給定元素屬於那種類型的路徑。
上面定義的集合C恰好包含了那些開始在A中的無限路徑所經過的A的元素。映射h接著被按如下方式定義，對於所有路徑它生成一個雙射，把在路徑中A的每個元素，映射到在路徑中直接前於或後於它的B的一個元素。對於在兩個方向上都是無限的路徑，和對於有限圈，我們選擇映射所有元素到它在路徑中的前驅。
