集合论中康托定理怎么证明 (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），接着再看更方便。