集合论中康托定理怎么证明

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}

假设幂集P(A) 的元素(即 A 的子集，即某个二进制数组)，始终有来自 A 的元素 αᵢ 与之对映，那么可以写成一个列阵，例如这样排列：

α₁＝1 1 0 1 0 1 . . .

α₂＝1 0 0 0 0 1 . . .

α₃＝0 1 0 1 0 1 . . .

α₄＝1 1 0 1 1 1 . . .

α₅＝1 0 1 1 1 1 . . .

这个二进制数组的对角线(左上至右下)取出来，我们称为D：

D＝1 0 0 1 1 . . .

不论怎样排列，一旦确定了对映关系，D 就确定了。

可以说，D 变成了一个规则， A 的所有元素中，第 i 个元素的第 i 个数字必定等于 Dᵢ ( D 的第 i 个数)。

所以非 D ，即反转0和1，就是一个破坏了这个规则的数组，我们称它为 Ag ：

Ag＝0 1 1 0 0 . . .

既然Ag 也是一个数组，那么它也是 P(A) 中的元素， A 的一个子集。

但它是一个破坏了规则的数组，自然不在规则的对映方式之下。就是说，若有α₀＝Ag 放进列阵中，不论放在哪一行，比如放在 i 行， α₀ 第 i 个数字必定不等于Dᵢ，因此不存在 α₀ 。

换言之，A 的所有元素对映完了， P(A) 都还有剩，即|A|＜|P(A)| 。

通过这个例子可以直观的看到任何可数集的势都小于其幂集的势。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。