作者MathTurtle (恩典)
看板W-Philosophy
标题Re: [问题] Cantor's Theorm康托定理
时间Fri Dec 30 10:50:49 2005
※ 引述《MathTurtle (恩典)》之铭言：
: 标题: Re: [问题] Cantor's Theorm康托定理
: 时间: Fri Dec 30 00:28:41 2005
:
: ※ 引述《realove (realove)》之铭言：
: : ※ 引述《realove (realove)》之铭言：
: : : 标题: [问题] Cantor's Theorm康托定理
: : : 时间: Thu Dec 29 13:16:08 2005
: : : 再问一下 康托定理大概是讲什麽呢?
: : : 请众高手们回答吧
: : : 谢谢
: : : 推 RitsuN:这位兄台(学长学姊??)，连续的伸手文不太好呗 XDXD 12/29 13:41
: : 上一篇也算伸手吗?:p 我後来有些feedback, right? 呵
: : 这篇据我所知 小小补充一下 好像是说There is no set of all sets 避免有伸手之嫌
: : 但证明有人知道吗...
: Cantor's Theorem 是这个吗?
:
: 如果只是there is no set of all sets, 那证明并不难啊...
: (actually, 这应该算是ZF集合论里面所设的公设直接导出的结果吧...)
: 大致上是这样, 如果存在the set of all sets, let it be U,
: so by axiom we can form the set {x in U | x is not in x},
: 然後就会有矛盾。
:
: 真正technically的证明应该会更复杂一点, 不过大概的概念好像是这样...
:
: --
:
※ 发信站: 批踢踢实业坊(ptt.cc)
: ◆ From: 61.229.208.109
: → qtaro:hmmm...你说的是Russell's paradox吧 12/30 02:42
对...我觉得the set of all sets的问题应该和Russell's paradox比较有关。
Cantor's Theorem我刚才用google查了一下,
好像是讲这件事:
For any set X, the cardinality of the power set of X is larger than X,
in other words, card(P(X)) > card(X).
也就是说, 我们无法找到一个one to one correspondence 从 X 映到 P(X).
( P(X) := { A | A is a subset of X } )
因此, 不存在the set of all sets也可以看成是Cantor's theorem 的一个
简单的corollary.
而这个证明非常的技巧 (应该是Cantor所想到的):
Suppose now we have f to be a 1-1 correspondece from X to P(X)
then consider the set C = { x belongs to X | x doesn't belong to f(x) }
since C is a subset of X, hence C belongs to P(X);
but since f is an 1-1 onto mapping, hence there must be some x in X,
such that f(x) = C, say b. (i.e. f(b)=C)
But now, either b belongs to C, or b doesn't.
If b belongs to C, i.e. {x | x doesn't belong to f(x) },
hence b doesn't belong to f(b), hence b doesn't belong to C.
On the other hand, if b doesn't belong to C (=f(b)),
i.e. b doesn't belong to f(b), hence satisfying the condition of C,
hence b belongs to C.
It is a contradition, therefore, there is no such a function.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.229.205.76
※ 编辑: MathTurtle 来自: 61.229.205.76 (12/30 10:52)