【离散数学-集合论】无穷集合的基数 (2-2)

康托定理

定理1.|M|＜|2ᴹ|

|M|＜|2ᴹ|。

老师的证明思路

[证] 1ˉ A⊂2ᴹ，N~A

A＝{{X}|x∈M}

2° M ~ ←╳ 2ᴹ 反证法假若不然則∃φ，φ：M→ 2ᴹ φ是双射∀x∈M，φ(x)∈2ᴹ φ(x)⊆M

∃b，φ(b)＝ф∈2ᴹ

∃g，φ(g)＝M∈2ᴹ

√

x ∈φ(x)───好元素

＜

x ⋶ φ(x)───坏元素

＿＿＿＿＿＿＿＿＿＿＿＿

令T为M中所有坏元素之集

T⊂M. T∈2ᴹ

∃m∈M，使φ(m)=T

＿＿＿＿＿＿＿＿＿＿＿＿

m好 ⇒ m坏！

{

m坏 ⇒ m好！

证明：

令A＝{{x}|x ∈ M}，显然A⊂2ᴹ且A~M。因此M与2ᴹ的一个真子集对等。

我们采用反证法证明M与2ᴹ不对等。

如若不然，必然存在一个双射φ：M → 2ᴹ。对于∀x ∈ M，必然有φ(x)∈2ᴹ，即φ(x) ⊆ M，对于x而言，必然是下面两种情况之一：x∈φ(x)，x∉φ(x)。

若x∈φ(x)，则定义x为好元素；若x∉φ(x)，则定义x为坏元素。令T为所有坏元素的集合，由于φ(x)是双射(这里利用的是满射性质)，故而必然存在α∈M，使得φ(α)＝∅∈2ᴹ，存在b∈M，使得φ(b)＝M∈2ᴹ，显然α∉∅，b∈M，故而α是坏元素，b是好元素，因此可得∅ ⊂ T ⊂ M。

由于φ(x)是双射(这里利用的是满射性质)，必然存在c∈M使得φ(c)＝T∈2ᴹ，若c是好元素，则c∉T，但根据坏元素定义可得c是坏元素；若c是坏元素，则c∈T，但根据好元素定义可得c是好元素。一个元素不能既是坏元素，也是好元素，即∀x∈M，不能同时属于T和M\T，由此导出矛盾。

因此M与2ᴹ不对等。

证毕！

康托——波恩斯坦定理

定理1.设A，B为集

f：A→B，g：B→A.

若f，g是单射.則A~B

我们知道存在A到B的单射，等价于存在A到B子集的一一映射，故而康托——波恩斯坦定理还可以表述为：假定A' ⊆ A，B' ⊆ B，若A ~ B'，B ~ A'，则A ~ B。

基数的三歧性定理

❖对任意集合A，B，或者|A|＜|B|，或者|A|＝

|B|，或者|B|＜|A|，且不能有两个式子同时成立。

参考

参考 哈尔滨工业大学的网课 集合论与图论课程主页

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