作者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