Schroder-Bernstein Theorem的證明

[aletheia (cOnJeCTuRe)]

西哲板有提到類似的東西，
要證明自然數和整數一樣大之前，
通常需要 Schroder-Berstein theorem會比較方便點。

我把一些證明的想法寫出來，正式的證明就不寫。
Wiki上面應該也查的到。
http://en.wikipedia.org/wiki/Cantor-Bernstein_theorem

以下有些符號受限於編碼的關係，有些符號無法顯示，我也就不用正式的符號。
如果有仁人志士可以幫我改寫符號的話，樂意之至。

Schroder-Berstein Theorem
又叫 Cantor–Bernstein–Schroeder theorem:

For any set A and B, if A is dominated by B and B is dominated by A,
then A and B is equinumerous.

證明的想法如下：

首先為了說明A和B是equinumerous，
目標就是要找到一個函數Ｆ:A=B (這等號是波浪狀的，以下一樣)。

由定義可知 有兩個函數f:A<B , g:B<A
(這邊的符號是strickly dominated,不過我打不出來dominated就將就用吧)
如果我們要找出Ｆ:A->B　那很自然的要從f和g出發。

先從f開始
我們假定B有某個子集D：for any b 屬於D, for some a 屬於A, f(a)=b
這可以由f:A<B直接得出

let C 是這些a, 那麼f restrict to C: C=D, 這是因為f is injective function
好，那麼接著要找的東西就是for some g*:A\C = B\D
因為找到這個g*的話，那麼Ｆ就是f restrict to C和g*的big union
而且這Ｆ就是我們最終的目的。

這次再從g開始，如果我們可以證明g:B\D->A\C 不只是injective而且是onto的話，
那麼the inverse of g:A\C = B\D 這就是g*

所以這證明的關鍵在於怎麼樣在A當中建立C，而使得f:C=D for some D of B
且使得the inverse of g:A\C = B\D

C看起來和g沒甚麼關係，這邊有個小訣竅，
只要在B當中不是for all a 屬於A f(a)的值，那麼他就是B/D
所以C現在就是A\g(B\D)

剩下的部分就不是很難了，接著要做的只是把A\ran(g)當作建立C最基本的單位
叫他C-0好了，而藉由f和g
我們可以做出一個C-1使得for all a'屬於C-1, a'=g(f(a)) for some a屬於C-0
同樣的，可以繼續這樣做出C-2,C-3,C-4......

好那現在把所有的C-n和D-n(D-0是all value of f(a), for all a屬於C-0)
放在一起的話
那麼f:Un Ci = Un Di (這邊我把i屬於N直接寫成n)

而這個Un Ci就是我們要找的C了
差不多就這樣


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.201.196
→ aletheia:應該不會有錯了 除了符號非常難看之外
※ 編輯: aletheia        來自: 220.134.201.196      (10/14 11:33)
推 yauhh:我有個小問題,證這個的人有什麼原因想證這個題目?
→ aletheia:你是說為什麼要證S-B theorem嗎
推 yauhh:直覺上自然數跟實數差很多,證S-B是要套用而證兩數系一樣多嗎
推 yauhh:哦,抱歉我看錯了,是自然數和整數
推 ERT312:他一開始的確是想證"自然數與實數一樣大"
→ ERT312:我在回文提醒他:那他鐵定不能用cantor的定義!
→ ERT312:我的回文被他坎了，我想他大概也不知道他在證什麼吧@@
→ ERT312:坎我的回文再偷改自己的文章，定義集合都不會
→ ERT312:這就是本板板主 = =
→ aletheia:我是想證自然數和整數一樣大 你去看西哲板的討論就知道
推 ERT312:你一開始是寫 自然數與實數 我有冤枉你嗎?
→ aletheia:我原本的用意了 刪你的文章是因為這是已結案的文章
→ ERT312:你還坎了我的回文 我沒說錯吧
→ aletheia:你又沒有提供任何建設性的意見 當然就刪掉了
→ ERT312:所以你坎文的標準是:有沒有建設性?
→ aletheia:我一開始寫錯了 後來更正 這樣也不被你允許嗎
→ ERT312:我只想說你亂坎別人的文章，太卑鄙了吧
→ ERT312:你寫錯當然可以更正，你之前亂定義集合，不也更正的很好
→ ERT312:但亂坎文就不應該。
→ aletheia:我沒有亂砍文 這板刪文的判準是你訂的嗎
→ ERT312:建議你想這些東西，轉到數學系吧，不要把生命浪費在
→ aletheia:我確實不應該把生命浪費在你這種人身上 言盡於此了
→ ERT312:文字遊戲上的爭辯。
→ ERT312:轉不過去，也可以自己自修。XDD
→ ERT312:看你 112的才好心建議你，聽不聽得進去看你的造化了。
推 yauhh:別鬧了,翻了Proof of the Book的確將實數證為不可數,有理數
→ yauhh:和整數證為可數,然後談bijection. 相信他只是一時打錯而已,
→ yauhh:312當你說一定不能用Cantor,我會冒出個問號:"要不然是要用什
→ yauhh:麼?" 指出錯處不是這樣指的,因為別人會期待你提出替代方案.