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

維基百科,自由的百科全書

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

證明[編輯]

下面是證明:

證明:

並令

對任意的 aA 定義映射

如果a不在集合C中,那麼a不在集合C0中。因此由C0的定義可知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)。由 C0 的定義知,a 不屬於 C0。由於 f[Cn] 是 f[C]的一個子集,因而 b 不屬於任何一個 f[Cn]所以由集合Cn的遞歸定義以及g為單射(不存在b以外的)的事實知,a = g(b) 不屬於 Cn+1= g[f[Cn]] (若屬於,則b和f[Cn]可互換)。因此,a 不屬於 CC0Cn)那麼根據h的定義 b = g–1(a) = h(a)。
  • 單射:h(a)=h(b),則有aCbC, aCbC, aCbC, aCbC四種情況。對於前兩種情況,由fg–1是單射得a=b。對於第三種情況,有f(a)=g–1(b)⇒g(f(a))=g(g–1(b))⇒g°f(a)=b,又由前提aC,而Cg°f下封閉,於是bC,但是由前提得bC,矛盾了,因此第三種情況不可能出現。同理,不失一般性,第四種情況也不可能出現,這說明ran(f|C) ∩ ran(g–1|A\C) = ∅。綜上若h(a)=h(b),一定有a=b

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

可視化[編輯]

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

example of the definition of h

顯示的是部分的(不相交)集合 AB ,以及映射 fg的一部分。如果集合 AB,與兩個映射一起,被詮釋為一個有向圖,則這個雙向圖有多個連接起來的構件(component)。

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

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

最初的證明[編輯]

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

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

引用[編輯]