集合基数[通俗易懂]

　　　　f：N×N→N
　　　　f(<m，n>)=+m

等势的性质

　　以上已经给出了若干等势的集合。一般说来，等势具有下面的性质：自反性，对称性和传递性。
  定理9.1 设A，B，C是任意集合，

　　(1) A≈A。

　　(2) 若A≈B，则B≈A。

　　(3) 若A≈B，B≈C，则A≈C。

　　证明:
根据前面的分析和这个定理可以得到下面的结果：

　　　　N≈Z≈Q≈N×N

　　　　R≈[0，1]≈(0，1)

　　而后一个结果可以进一步强化成：任何的实数区间(包括开区间，闭区间以及半开半闭的区间)都与实数集合R等势。那么N与R是否等势呢?如果有N≈R，上面列出的所有集合彼此都是等势的；如果NR，与N等势的那些集合也不会与R等势。下面证明NR。

定理9.2 (康托定理)

　　(1) NR

　　(2) 对任意集合A都有AP(A)。

　　证 (1)如果能证明N[0,1]，就可以断定NR.为此只需证明任何函数f：N→[0,1]都不是满射的。

　　首先规定[0，1]中数的表示。对任意的x∈[0,1]，令

　　　　x=0.x₁x₂…，0≤x_i≤9

考察下述两个表示式：

　　　　0.24999… 和 0.25000…

显然它们是同一个x的表示。为了保证表示式的唯一性，如果遇到上述情况，则将x表示为0.25000…。根据这种表示法，任何函数f： N→[0，1]的值都可以用这种表示式给出。

　　设f： N→[0,1]是从N到[0,1]的任何一个函数。如下列出f的所有函数值：

　　　　f(0)=0.a₁⁽¹⁾a₂⁽¹⁾…

　　　　f(1)=0.a₁⁽²⁾a₂⁽²⁾…

　　　　…

　　　　f(n-1)=0.a₁⁽ⁿ⁾a₂⁽ⁿ⁾…

　 　 　…

设y是[0,1]之中的一个小数，y的表示式为0.b₁b₂…，并且满足b_i≠a_i⁽ⁱ⁾，i=1，2，….显然y是可以构造出来的，且y与上面列出的任何一个函数值都不相等。这就推出yranf，即f不是满射的。

　　(2)和(1)的证明类似，我们将证明任何函数g：A→P(A)都不是满射的。

　　设g： A→P(A)是从A到P(A)的函数，如下构造集合B：

　　　　B={x|x∈A∧xg(x)}

则B∈P(A)，但对任意x∈A都有

　　　　x∈Bxg(x)

从而证明了对任意的x∈A都有B≠g(x)。即Brang。

优势

定义9.2
　　(1) 设A，B是集合，如果存在从A到B的单射函数，就称B优势于A，记作A·B。如果B不是优势于A，则记作A·B。
　　(2) 设A，B是集合，若A·B且AB，则称B真优势于A，记作A·B。如果B不是真优势于A，则记作A·B。
　　例如N·N，N·R，A·P(A)，R·N。 又如N·R，A·P(A)，但N·N。
　　优势具有下述的性质。
定理9.3 设A，B，C是任意的集合，则

　　(1)A·A。

　　(2)若A·B且B·A，则A≈B。

　　(3)若A·B且B·C，则A·C。

　　定理9.3(2)部分的证明比较复杂，已经超过本书范围，故而略去。(1)和(3)的证明留作练习。

9.2 集合的基数

一．后继与归纳集

　　　　⁺=∪{
}={
}

　　　　⁺⁺={
}⁺={
}∪{
{
}}={
，{
}}={
，⁺}

　　　　⁺⁺⁺={
，{
}}⁺={
，{
}}∪{
{
，{
}}}

　　 　 　　　={
，{
}，{
，{
}}}

　　 　 　　　={
，⁺，⁺⁺}

　　由于对任何集合a都有aa。在空集的一系列后继中，任何两个集合都不相等。且满足下面的两个条件：

　　　　0=

　　　　1=0⁺=⁺={
}={0}

　　　　2=1⁺={
}⁺={
，{
}}={0，1}

自然数,有穷集,无穷集

 定义9.4 设A为集合,如果满足下面的两个条件：
　　（1）∈A
　　（2）a(a∈A→a⁺∈A)
则称A是归纳集。
　　例如下面的集合
　　　　{
,⁺,⁺⁺,⁺⁺⁺,…}
　　　　{
,⁺,⁺⁺,⁺⁺⁺,…,a,a⁺,a⁺⁺,a⁺⁺⁺,…}
都是归纳集。
定义9.5
　　（1）一个自然数n是属于每一个归纳集的集合。
　　（2）自然数集N是所有归纳集的交集。
　　不难看出，根据定义9.5得到的自然数集N恰好由,⁺,⁺⁺,⁺⁺⁺,…等集合构成。而这些集合正是构造行所定义的全体自然数。
　　鉴于自然数都是集合，有关集合的运算对自然数都是适用的，例如：
　　　　2∪5={0,1}∪{0,1,2,3,4}={0,1,2,3,4}=5
　　　　3∩4={0,1,2}∩{0,1,2,3}={0,1,2}=3
　　　　4-2={0,1,2,3}-{0,1}={2,3}
　　　　2×3={0,1}×{0,1,2}={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}
　　　　P(1)=P({0})={
,{0}}={0,1}
　　　　2³={0,1}^{0,1,2}={f|f：{0,1,2}→{0,1}}={f₀,f₁,…,f₇}
　　其中
　　　　f₀={<0,0>,<1,0>,<2,0>}
　　　　f₁={<0,0>,<1,0>,<2,1>}
　　　　f₂={<0,0>,<1,1>,<2,0>}
　　　　f₃={<0,0>,<1,1>,<2,1>}
　　　　f₄={<0,1>,<1,0>,<2,0>}
　　　　f₅={<0,1>,<1,0>,<2,1>}
　　　　f₆={<0,1>,<1,1>,<2,0>}
　　　　f₇={<0,1>,<1,1>,<2,1>}

基数

　　下面给出基数的定义。
定义9.7
　　（1）对于有穷集合A，称与A等势的那个唯一的自然数为A的基数，记作cardA，即
　　　　cardA=nA≈n （对于有穷集A，cardA也可以记作|A|）
　　（2）自然数集合N的基数记作，即
　　　　cardN=₀
　　（3）实数集R的基数记作（读作阿列夫），即
　　　　cardR=
　　下面定义基数的相等和大小。

定义9.8 设A，B为集合，则
　　（1）cardA=cardBA≈B
　　（2）cardA≤cardBA·B
　　（3）card<cardBcardA≤cardB∧cardA≠cardB
　　根据上一节关于势的讨论不难得到：
　　　　cardZ=cardQ=cardN×N=₀
　　　　cardP(N)=card2^N=card[a，b]=card(c，d)=
　　　　₀<
其中2N={0，1}N。从这里可以看出，集合的基数是集合的势的大小的度量。基数越大，势就越大。


　　由于对任何集合A都满足A·P(A)，所以有
　　　　cardA<cardP(A)


这说明不存在最大的基数。将已知的基数按从小到大的顺序排列就得到：
　　　　0，1，2，…，n，…，₀，…
其中0，1，2…，n，…，恰好是全体自然数，是有穷集合的基数，也叫有穷基数。而₀，，…，是无穷集合的基数，也叫做无穷基数，₀是最小的无穷基数，而后面还有更大的基数，如cardP(R)等。

可数集

定义9.9 设A为集合，若cardA≤₀，则称A为可数集或可列集。

　　（2）由B=，可知cardB=0。

　　　　cardA=₀，cardB=n，n是自然数，n≠0。

　　解 由cardA=₀，cardB=n，可知A，B都是可数集。令

　　　　<a_i,b_j>=<a_k,b_l>i=k∧j=l

　　　cardA×B=cardN=₀

　　如果直接使用可数集的性质，本题的求解更为简单。因为cardA=₀，cardB=n，所以A，B都是可数集。根据性质3可知A×B也是可数集，所以cardA×B≤₀。显然当B≠时，cardA≤cardA×B，这就推出cardA×B=₀。

习题

1.设A={a,b,c}，B=2^A，由定义证明P(A)≈2^A。
2.设[1，2]和[0，1]是实数区间，由定义证明[1，2]≈[0，1]。
3.设A={2x|x∈N}，证明A≈N。
4.证明定理9.1。
5.证明定理9.3的(1)，(3)。
6.设A，B，C，D是集合，且A≈C，B≈D，证明A×B≈C×D。
7.找出三个不同的N的真子集，使得他们都与N等势。
8.找出三个不同的N的真子集A，B，C，使得A·N，B·N，C·N。
9.根据自然数的集合定义计算：
　(1)3∪6，2∩5
　(2)4-3，31
　(3)∪4，∩1
　(4)1×4，2²

10.设A，B为可数集，证明　(1)A∪B是可数集。　(2)A×B是可数集。

关于Discrete Mathematics更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.