※ 引述《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)