数学联邦政治世界观
超小超大

集合论中康托定理怎么证明 (2-1)

cantor定理是说,任意集合的势(元素的数量)小于其幂集(其所有子集构成的集合)的势。

对于任意两个集合A 和 B ,满射: A surj B 意味着他们的势: |A| ≥ |B|

所以非满射: not A surj B 意味着 |A|<|B|

所以要证明一个集合A 小于其幂集 P(A),则只用证明不是满射的即可。

如果A surj P(A),那意味着 P(A)中每个元素至少拥有一个从 A 的元素映射过来的箭头,所以若能证明 P(A) 中有个元素(即 A 的一个子集)它没有映射箭头即可证明非满射。

我们用g 表示映射函数,那么就是说,找到 A 的一个不被 g 作用的子集即可。

我们将这个子集(也就是P(A) 的一个元素)用 Ag 表示:

Ag∷={α ∈ A│α ∉ g(α)}

现在证明,P(A) 中Ag 没有映射箭头(即 A 中没有元素能与之对映):

用反证法,假设 A 中有这个元素对映Ag ,我们称这个元素为 α₀ ,即:

A(g)=g(α₀)

A P(A)

∶ ∶

∶ ∶

∶ g ∶

α₀∶} → {∶

∶↘ ∶

∶ ∶↙Ag

Ag{∶

∶↗

α₀

那么,这个A 中的元素 α₀ 在 A 中的哪个地方?在不在 A 的子集 Ag 里?

• 若在,那么意味着 α₀ 也满足 Ag 的定义,即不被 g 作用(也就是没有箭头):α₀ ∉ g(α₀)

这与α₀ 有箭头指向 Ag 这个前提假设相矛盾。

• 若不在,则意味着 α₀ 被 g 作用,满足 α₀ ∈ g(α₀),但是 Ag=g(α₀),所以 α₀ 又在 Ag 里面,矛盾。

α₀ 没有容身之地,所以不存在 α₀ 映射 P(A) 中的 Ag ,即非满射,即 |A|<|P(A)|。

还有一个更直观的方法可以看到这一现象:(对角论证法)

集合的子集,可以用二进制数组表示,其中0表示没有,1表示有,并假设这些子集可以按一定顺序列出来(可数的)。

例如:集合{A,B,C},其子集有:{A,B,C},{A,B},{AC},{B,C},{A},{B},{C},{}

分别对映二进制数组{1,1,1},{1,1,0},{1,0,1},{0,1,1},{1,0,0},{0,1,0},{0,0,1},{0,0,0}

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

重铸:繁尽花海 连载中
重铸:繁尽花海
屑鸽子作者
看我看我看我,快来看我啊求你了(இωஇ)Q群:916270014(无聊的作者渴望你加个群,欢迎催更)(本文大致可以算作是前传吧,应该会长期更......
0.1万字8个月前
悲观主义水流的笑之岩 连载中
悲观主义水流的笑之岩
时令性决堤
第五人格(主宿伞之魂,多cp)、oc、随感大杂烩,主观性强,观赏性差,不建议阅读。
0.1万字8个月前
重来(无限) 连载中
重来(无限)
颜星荼
0.3万字8个月前
落魄成Omega后我被强行揣崽 连载中
落魄成Omega后我被强行揣崽
郁季
13.8万字8个月前
非人哉相处日常 连载中
非人哉相处日常
傲娇兔本兔
五个大佬妖怪的宠溺,与妖怪的相处日常。
23.1万字8个月前
破月(双女主) 连载中
破月(双女主)
浮生琐
短篇,修仙,双女主
0.4万字8个月前