西哲板有提到類似的東西，
要證明自然數和整數一樣大之前，
通常需要 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