[科普中國]-康托爾-伯恩施坦定理

康托爾-伯恩施坦定理也叫作定理****康托爾-伯恩斯坦-施羅德定理（Cantor-Bernstein-Schroeder theorem），是集合論中的一個基本定理，得名于康托爾、伯恩斯坦和 Ernst Schr?der。

簡介康托爾-伯恩斯坦定理（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等勢。顯然，這是在基數排序中非常有用的特征。

證明下面是證明：1

**證明：**令

并令

對任意的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的定義可透過右圖展示。

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

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

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

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

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

本詞條內容貢獻者為:

胡建平 - 副教授 - 西北工業(yè)大學