作者aletheia (cOnJeCTuRe)
看板logic
標題Schroder-Bernstein Theorem的證明
時間Tue Oct 14 01:26:27 2008
西哲板有提到類似的東西，
要證明自然數和整數一樣大之前，
通常需要 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
1F：→ aletheia:應該不會有錯了 除了符號非常難看之外 10/14 01:30
※ 編輯: aletheia 來自: 220.134.201.196 (10/14 11:33)
2F：推 yauhh:我有個小問題,證這個的人有什麼原因想證這個題目? 10/14 12:07
3F：→ aletheia:你是說為什麼要證S-B theorem嗎 10/14 12:20
4F：推 yauhh:直覺上自然數跟實數差很多,證S-B是要套用而證兩數系一樣多嗎 10/14 13:22
5F：推 yauhh:哦,抱歉我看錯了,是自然數和整數 10/14 13:25
6F：推 ERT312:他一開始的確是想證"自然數與實數一樣大" 10/14 16:09
7F：→ ERT312:我在回文提醒他:那他鐵定不能用cantor的定義! 10/14 16:10
8F：→ ERT312:我的回文被他坎了，我想他大概也不知道他在證什麼吧@@ 10/14 16:11
9F：→ ERT312:坎我的回文再偷改自己的文章，定義集合都不會 10/14 16:12
10F：→ ERT312:這就是本板板主 = = 10/14 16:13
11F：→ aletheia:我是想證自然數和整數一樣大 你去看西哲板的討論就知道 10/14 16:27
12F：推 ERT312:你一開始是寫 自然數與實數 我有冤枉你嗎? 10/14 16:28
13F：→ aletheia:我原本的用意了 刪你的文章是因為這是已結案的文章 10/14 16:28
14F：→ ERT312:你還坎了我的回文 我沒說錯吧 10/14 16:28
15F：→ aletheia:你又沒有提供任何建設性的意見 當然就刪掉了 10/14 16:28
16F：→ ERT312:所以你坎文的標準是:有沒有建設性? 10/14 16:29
17F：→ aletheia:我一開始寫錯了 後來更正 這樣也不被你允許嗎 10/14 16:29
18F：→ ERT312:我只想說你亂坎別人的文章，太卑鄙了吧 10/14 16:31
19F：→ ERT312:你寫錯當然可以更正，你之前亂定義集合，不也更正的很好 10/14 16:31
20F：→ ERT312:但亂坎文就不應該。 10/14 16:32
21F：→ aletheia:我沒有亂砍文 這板刪文的判準是你訂的嗎 10/14 16:34
22F：→ ERT312:建議你想這些東西，轉到數學系吧，不要把生命浪費在 10/14 16:34
23F：→ aletheia:我確實不應該把生命浪費在你這種人身上 言盡於此了 10/14 16:35
24F：→ ERT312:文字遊戲上的爭辯。 10/14 16:35
25F：→ ERT312:轉不過去，也可以自己自修。XDD 10/14 16:36
26F：→ ERT312:看你 112的才好心建議你，聽不聽得進去看你的造化了。 10/14 16:37
27F：推 yauhh:別鬧了,翻了Proof of the Book的確將實數證為不可數,有理數 10/15 23:12
28F：→ yauhh:和整數證為可數,然後談bijection. 相信他只是一時打錯而已, 10/15 23:13
29F：→ yauhh:312當你說一定不能用Cantor,我會冒出個問號:"要不然是要用什 10/15 23:14
30F：→ yauhh:麼?" 指出錯處不是這樣指的,因為別人會期待你提出替代方案. 10/15 23:16