Schroder-Bernstein Theorem的證明

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