1/73第六章第六章 集合的基数集合的基数在前面我们的基数简单的看作集合元素的个数，这在前面我们的基数简单的看作集合元素的个数，这对于有限集来说没有问题，但对于无限集而言，对于有限集来说没有问题，但对于无限集而言，““元素的个数元素的个数””这个概念是没有意义的，那么两这个概念是没有意义的，那么两个集合的个集合的““大小大小””，，““相同相同””的确切含义是什么的确切含义是什么呢？形式的描述元素呢？形式的描述元素““多少多少””的概念数学工具是的概念数学工具是函数先讨论自然数集合，有限集，无限集先讨论自然数集合，有限集，无限集 2/73第六章第六章 集合的基数集合的基数•定义定义6.16.1：：设设S S为任意集合，为任意集合，S∪{S}S∪{S}称为称为S S的后继集的后继集合，记为合，记为 ，显然，显然 例：令例：令 ，则，则 可以构造出集合序列：可以构造出集合序列：将上面的集合依次命名为将上面的集合依次命名为0,1,20,1,2，，……，就可构造出自，就可构造出自然数，用然数，用““:=:=””来命名；即来命名；即一般地：一般地：自然数集自然数集N={0,1,2N={0,1,2，， ……} } 3/73第六章第六章 集合的基数集合的基数•G G•PeanoPeano将自然数所组成的集合的基本特征描述为将自然数所组成的集合的基本特征描述为下列公理；设下列公理；设N N表示自然数集合，则表示自然数集合，则其中其中(3)(3)说明了说明了N N是满足条件是满足条件(1)(1)，，(2)(2)的最小集合，的最小集合，(3)(3)也称为极小性质。
也称为极小性质•定义定义6.26.2：：如存在集合如存在集合{0,1,2{0,1,2，， ……，，n-1}(n-1}(自然数自然数n)n)到到A A或或A A到集合到集合{0,1,2{0,1,2，， ……，，n-1}n-1}的双射，则集的双射，则集合合A A称为有限集，否则称为无限集称为有限集，否则称为无限集•定理定理6.16.1：：自然数集自然数集N N为无限集为无限集 4/73第六章第六章 集合的基数集合的基数证明：只要证明证明：只要证明N N不是有限集，反证法不是有限集，反证法设设N N为有限集，即存在为有限集，即存在f f是是{0,1,2{0,1,2，，……，，n-1}n-1}到到N N的双的双射，现令射，现令 ，显，显然对然对i=0,1,i=0,1,……,n-1,n-1，恒有，恒有f(if(i)
有限集的任何子集均为有限集证明：设证明：设S S为有限集，因而有双射为有限集，因而有双射f f，自然数，自然数n n，，f: f: {0,1,{0,1,……，，n-1}→Sn-1}→S，因此，因此S={f(0),f(1),S={f(0),f(1),……，，f(n-f(n-1)}1)}，若，若 为为S S的任一子集，则的任一子集，则 为为{0,1,2{0,1,2，，……，，n-1}n-1}中的不同成中的不同成员将序列员将序列 看作看作{0,1,2{0,1,2，，……，，k-1}k-1}到到 的双射，记为的双射，记为g g，， 5/73第六章第六章 集合的基数集合的基数那么：那么： 为双射，因此，为双射，因此，A A为为有限集•定理定理6.36.3：：任何含有无限子集的集合必定是无限集任何含有无限子集的集合必定是无限集此定理是此定理是6.26.2的逆否命题，所以也成立。
的逆否命题，所以也成立•定理定理6.46.4：：无限集必与它的一个真子集存在双射函无限集必与它的一个真子集存在双射函数证明：设证明：设S S为任一无限集，显然为任一无限集，显然 ，可取元素，可取元素 ，考虑，考虑 ，， 仍为非空无限集，又在仍为非空无限集，又在 中中可取可取 ，考虑，考虑 ，， 仍为非空无限集，仍为非空无限集，同样有同样有 令令 ，显然，显然 ，，且对任一自然数且对任一自然数n n，总有，总有 ，令，令 定定义函数义函数 为：为： 6/73第六章第六章 集合的基数集合的基数易知易知f f为一双射，为一双射，∴∴命题成立命题成立•推论：推论：凡不能与自身的任意真子集之间存在双射函凡不能与自身的任意真子集之间存在双射函数的集合为有限集合数的集合为有限集合•定义定义6.36.3：如果存在从：如果存在从N N到到S S的双射，则称集合的双射，则称集合S S为可为可数无限集数无限集( (ConntableConntable Infinite Sets) Infinite Sets)。
其它无限其它无限集称为不可数无限集有限集合和可数无限集统集称为不可数无限集有限集合和可数无限集统称为可数集称为可数集( (不可数集即不可数无限集不可数集即不可数无限集) ) 显然，显然，N N是可数集，是可数集，N N可以排成一个无穷序列的形式：可以排成一个无穷序列的形式：0,1,20,1,2，，……因此，其它任何可数集合因此，其它任何可数集合S S中的元素也中的元素也可以排成一个无穷序列可以排成一个无穷序列 7/73第六章第六章 集合的基数集合的基数一个集合是可数集的充要条件是它的元素可以排成一个集合是可数集的充要条件是它的元素可以排成一个无穷序列的形式一个无穷序列的形式•定理定理6.56.5：：整数集为可数无限集整数集为可数无限集证：建函数：证：建函数：f:Z→Nf:Z→N：：易知易知f(xf(x) )为一双射，为一双射，∴∴Z Z为可数集为可数集•定理定理6.66.6：：任何无限集必有一个可数子集任何无限集必有一个可数子集证：类似于证：类似于6.46.4，从无限集中依次取出一列元素，构，从无限集中依次取出一列元素，构成一个可数集成一个可数集 8/73第六章第六章 集合的基数集合的基数•定理定理6.76.7：：可数集的任何无限子集必为可数集。
可数集的任何无限子集必为可数集证：设证：设S S是可数集，是可数集，S S中的元素可以排成：中的元素可以排成： ，设，设B B是是S S的任一无限子集，它的元素也是的任一无限子集，它的元素也是S S的元素，的元素，并且它可排成：并且它可排成： ，，∴∴B B是可数集是可数集•定理定理6.86.8：：可数集中加入有限个元素可数集中加入有限个元素( (或删除有限个或删除有限个元素元素) )仍为可数集仍为可数集证：设证：设 是可数集，不妨在是可数集，不妨在S S中加入有限个中加入有限个元素元素 ，且它们均与，且它们均与S S的元素不相同，得的元素不相同，得到新的集合到新的集合B B，它的元素也可排成无穷序列：，它的元素也可排成无穷序列： ∴∴B B是可数集是可数集 9/73第六章第六章 集合的基数集合的基数•定理定理6.96.9：：两个可数集的并集是可数集两个可数集的并集是可数集证：设证：设 均为可数集，均为可数集，不妨设不妨设 不相交，不相交， 元素可以排成无穷序元素可以排成无穷序列：列： 为可数集。
为可数集•推论：推论：有限个可数集的并是可数集有限个可数集的并是可数集•定理定理6.106.10：：可数个可数集的并集是可数集可数个可数集的并集是可数集证：不失一般性，设这可数个可数集均非空，且互证：不失一般性，设这可数个可数集均非空，且互不相交：不相交： 10/73第六章第六章 集合的基数集合的基数当当 为有限集为有限集 时，令时，令从而从而 ，，S S中元素排列为：中元素排列为： ∴S ∴S为可数集为可数集ØN N××N N是可数集；有理数是可数集是可数集；有理数是可数集( (证明见书证明见书) )•定理定理6.116.11：：实数集的子集实数集的子集[0,1][0,1]区间是不可数集区间是不可数集证：用反证法设证：用反证法设[0,1][0,1]为可数集为可数集 ，由于，由于[0,1][0,1]中的实数均可表示为十进制无限小数，因此中的实数均可表示为十进制无限小数，因此[0,1][0,1]中的实数可如下列出：中的实数可如下列出： 11/73第六章第六章 集合的基数集合的基数现作一个十进制小数现作一个十进制小数 其中：其中：显然，显然，y y满足满足且对任意且对任意n n，因为，因为 ，所以，所以y y与与 中的任中的任何一个数都不相同，即何一个数都不相同，即 ，矛盾，，矛盾， ∴∴[0,1][0,1]是不可数集。
是不可数集•定义定义6.46.4：：如果有双射如果有双射f:{0,1,2,f:{0,1,2,……,n-1}→S,n-1}→S，或双，或双射射f:S→{0,1,2,f:S→{0,1,2,……,n-1},n-1}，则称集合，则称集合S S的基数的基数(Cardinal number)(Cardinal number)为为n(nn(n为自然数为自然数) )记为|S|=n|S|=n，显然：集合，显然：集合S S为有限集，当且仅当它以自然数为为有限集，当且仅当它以自然数为其基数，即存在自然数其基数，即存在自然数n n使得使得|S|
Ø实数集的任何闭区间实数集的任何闭区间[a, b][a, b]，开区间，开区间(a, b)(a, b)以及以及实数集本身都是连续统实数集本身都是连续统 13/73第六章第六章 集合的基数集合的基数是否所有机会都以自然数是否所有机会都以自然数n, n, ，和，和c c之一作为其基之一作为其基数呢？为此我们引入基数大小的概念：数呢？为此我们引入基数大小的概念：•定义定义6.76.7：：设设A A，，B B为任意集合为任意集合(1)(1)如果有双射如果有双射f:A→Bf:A→B或双射或双射f:B→Af:B→A，则称，则称A A和和B B基数基数相等，记为相等，记为|A|=|B||A|=|B|；；(2)(2)如果有单射如果有单射f:A→Bf:A→B或满射或满射f:B→Af:B→A，则称，则称A A的基数的基数小于等于小于等于B B的基数，记为的基数，记为|A|≤|B||A|≤|B|；；(3)(3)如果如果|A|≤|B||A|≤|B|，且，且|A| |B||A| |B|，则称，则称A A的基数小于的基数小于B B的基数，记为的基数，记为|A|<|B||A|<|B| 14/73第六章第六章 集合的基数集合的基数Ø(1)(1)对任意自然数对任意自然数m≤nm≤n，则，则|{0,1,2, |{0,1,2, ……,m-1}| ≤ ,m-1}| ≤ |{0,1,2, |{0,1,2, ……,n-1}|;,n-1}|;Ø(2)(2)对以上自然数对以上自然数n, n< n, n< ，即，即|{0,1,2, |{0,1,2, ……,n-,n-1}| ≤|{0,1,2, 1}| ≤|{0,1,2, ……}|;}|;Ø(3)
决的理论问题•定理定理6.126.12：：对任意集合对任意集合A A，，B B，，C C有有(1)|A|≤|A|(1)|A|≤|A|；；(2)|A|≤|B|(2)|A|≤|B|，，|B|≤|C||B|≤|C|，则，则|A|≤|C||A|≤|C|•定理定理6.136.13：：对任意集合对任意集合A A，，B B，或者，或者|A|<|B||A|<|B|，或者，或者|A|=|B||A|=|B|，或者，或者|B|<|A||B|<|A|，且任意两者都，且任意两者都 不能兼而不能兼而有之 15/73第六章第六章 集合的基数集合的基数•定理定理6.146.14：：对任意集合对任意集合A A，，B B，若，若|A|≤|B||A|≤|B|，，|B| |B| ≤|A|≤|A|，则，则|A|=|B||A|=|B|证：设证：设|A| |B||A| |B|，则或，则或|A|<|B||A|<|B|，或，或|B|<|A||B|<|A|且不能且不能兼而有之，而兼而有之，而|A|≤|B||A|≤|B|，，|B| ≤|A||B| ≤|A|，矛盾例：例：P(N)(NP(N)(N为自然数集为自然数集) )额为连续统额为连续统。
证：建立单射证：建立单射f:P(N)→[0,1]f:P(N)→[0,1]和单射和单射g:[0,1]→P(N)g:[0,1]→P(N)即可定义定义f:P(N)→[0,1]f:P(N)→[0,1]如下： 16/73第六章第六章 集合的基数集合的基数定义定义g:[0,1]→P(N)g:[0,1]→P(N)如下：对每一对每一[0,1][0,1]中数的二进制表示中数的二进制表示( (如果这种表示不唯如果这种表示不唯一，则取定其中之一一，则取定其中之一) )•定理定理6.156.15：：( (康托定理康托定理) )设设M M为任意集合，记为任意集合，记M M的幂集的幂集为为S S，则，则|M|<|S||M|<|S|证：对任意集合证：对任意集合M M，当，当M= M= 时，显然时，显然|M|=0|M|=0，，|S|=1|S|=1，成立；，成立；当当 时，对时，对 ，因此如下函，因此如下函数数f:M→Sf:M→S明显为一单射，即对每个明显为一单射，即对每个 ，，所以所以|M|<|S||M|<|S|；； 17/73第六章第六章 集合的基数集合的基数现证明现证明|M| |S||M| |S|，用反证法。
用反证法设设|M|=|S||M|=|S|，故有双射，故有双射g:M→Sg:M→S，使得对每一个，使得对每一个 有有唯一的唯一的 ，定义集合：，定义集合：当然当然 由于由于g g为双射，对为双射，对 ，有唯一的，有唯一的 ，使得，使得g(yg(y)=B)=B，而，而矛盾 ∴ ∴g g不存在，即不存在，即|M| |S||M| |S|，， ∴ ∴ |M|<|S| |M|<|S|Ø定理说明：没有最大的基数，也没有最大的集合定理说明：没有最大的基数，也没有最大的集合。