第六章 集合的基数 在前面我们的基数简单的看作集合元素的个数，这对于有限集来说没有问题，但对于无限集而言，“元素的个数”这个概念是没有意义的，那么两个集合的“大小”，“相同”的确切含义是什么呢？形式的描述元素“多少”的概念数学工具是函数。 先讨论自然数集合，有限集，无限集。

Presentation on theme: "第六章 集合的基数 在前面我们的基数简单的看作集合元素的个数，这对于有限集来说没有问题，但对于无限集而言，“元素的个数”这个概念是没有意义的，那么两个集合的“大小”，“相同”的确切含义是什么呢？形式的描述元素“多少”的概念数学工具是函数。 先讨论自然数集合，有限集，无限集。"— Presentation transcript:

1 第六章 集合的基数 在前面我们的基数简单的看作集合元素的个数，这对于有限集来说没有问题，但对于无限集而言，“元素的个数”这个概念是没有意义的，那么两个集合的“大小”，“相同”的确切含义是什么呢？形式的描述元素“多少”的概念数学工具是函数。 先讨论自然数集合，有限集，无限集。

2 第六章 集合的基数 定义6.1：设S为任意集合，S∪{S}称为S的后继集合，记为 ，显然 。 例：令 ，则 可以构造出集合序列：
例：令 ，则 可以构造出集合序列： 将上面的集合依次命名为0,1,2，…，就可构造出自然数，用“:=”来命名；即 一般地： 自然数集N={0,1,2， …}

3 第六章 集合的基数 G•Peano将自然数所组成的集合的基本特征描述为下列公理；设N表示自然数集合，则
定义6.2：如存在集合{0,1,2， …，n-1}(自然数n)到A或A到集合{0,1,2， …，n-1}的双射，则集合A称为有限集，否则称为无限集。 定理6.1：自然数集N为无限集。

4 第六章 集合的基数 证明：只要证明N不是有限集，反证法。
设N为有限集，即存在f是{0,1,2，…，n-1}到N的双射，现令 ，显然对i=0,1,…,n-1，恒有f(i)<L，这就是说f不是满射，矛盾。 ∴N不是有限集，是无限集。 定理6.2：有限集的任何子集均为有限集。 证明：设S为有限集，因而有双射f，自然数n，f: {0,1,…，n-1}→S，因此S={f(0),f(1),…，f(n-1)}，若 为S的任一子集，则 为{0,1,2，…，n-1}中的不同成员将序列 看作{0,1,2，…，k-1}到 的双射，记为g，

5 第六章 集合的基数 那么： 为双射，因此，A为有限集。 定理6.3：任何含有无限子集的集合必定是无限集
此定理是6.2的逆否命题，所以也成立。 定理6.4：无限集必与它的一个真子集存在双射函数。 证明：设S为任一无限集，显然 ，可取元素 ，考虑 ， 仍为非空无限集，又在 中可取 ，考虑 ， 仍为非空无限集，同样有 令 ，显然 ，且对任一自然数n，总有 ，令 定义函数 为：

6 第六章 集合的基数 易知f为一双射，∴命题成立。 推论：凡不能与自身的任意真子集之间存在双射函数的集合为有限集合。
定义6.3：如果存在从N到S的双射，则称集合S为可数无限集(Conntable Infinite Sets)。其它无限集称为不可数无限集。有限集合和可数无限集统称为可数集(不可数集即不可数无限集)。 显然，N是可数集，N可以排成一个无穷序列的形式：0,1,2，…因此，其它任何可数集合S中的元素也可以排成一个无穷序列

7 第六章 集合的基数 一个集合是可数集的充要条件是它的元素可以排成一个无穷序列的形式。 定理6.5：整数集为可数无限集。
证：建函数：f:Z→N： 易知f(x)为一双射，∴Z为可数集。 定理6.6：任何无限集必有一个可数子集。 证：类似于6.4，从无限集中依次取出一列元素，构成一个可数集。

8 第六章 集合的基数 定理6.7：可数集的任何无限子集必为可数集。
证：设S是可数集，S中的元素可以排成： ，设B是S的任一无限子集，它的元素也是S的元素，并且它可排成： ，∴B是可数集。 定理6.8：可数集中加入有限个元素(或删除有限个元素)仍为可数集。 证：设 是可数集，不妨在S中加入有限个元素 ，且它们均与S的元素不相同，得到新的集合B，它的元素也可排成无穷序列： ∴B是可数集。

9 第六章 集合的基数 定理6.9：两个可数集的并集是可数集。 证：设 均为可数集，不妨设 不相交， 元素可以排成无穷序列： 为可数集。
证：设 均为可数集，不妨设 不相交， 元素可以排成无穷序列： 为可数集。 推论：有限个可数集的并是可数集。 定理6.10：可数个可数集的并集是可数集。 证：不失一般性，设这可数个可数集均非空，且互不相交：

10 第六章 集合的基数 当 为有限集 时，令 从而 ，S中元素排列为： ∴S为可数集。 N×N是可数集；有理数是可数集(证明见书)。
当 为有限集 时，令 从而 ，S中元素排列为： ∴S为可数集。 N×N是可数集；有理数是可数集(证明见书)。 定理6.11：实数集的子集[0,1]区间是不可数集。 证：用反证法。设[0,1]为可数集 ，由于[0,1]中的实数均可表示为十进制无限小数，因此[0,1]中的实数可如下列出：

11 第六章 集合的基数 现作一个十进制小数 其中： 显然，y满足
现作一个十进制小数 其中： 显然，y满足 且对任意n，因为 ，所以y与 中的任何一个数都不相同，即 ，矛盾， ∴[0,1]是不可数集。 定义6.4：如果有双射f:{0,1,2,…,n-1}→S，或双射f:S→{0,1,2,…,n-1}，则称集合S的基数(Cardinal number)为n(n为自然数)。记为|S|=n，显然：集合S为有限集，当且仅当它以自然数为其基数，即存在自然数n使得|S|<n。

12 第六章 集合的基数 定义6.5：如果有双射f:N→S，或双射f:S→N，N为自然数集，称集合S的基数为S ，记为|S|= ；读作阿列夫零。
自然数集合一切可数无限集的基数均为 。 定义6.6：如果有双射f:[0,1]→S或双射f:S→ [0,1]，则称集合S的基数为c也记为 ，读作阿列夫，记为|S|=c，具有基数c的集合常称为连续统(antinuum)。 实数集的任何闭区间[a, b]，开区间(a, b)以及实数集本身都是连续统。

13 第六章 集合的基数 是否所有机会都以自然数n, ，和c之一作为其基数呢？为此我们引入基数大小的概念： 定义6.7：设A，B为任意集合
(1)如果有双射f:A→B或双射f:B→A，则称A和B基数相等，记为|A|=|B|； (2)如果有单射f:A→B或满射f:B→A，则称A的基数小于等于B的基数，记为|A|≤|B|； (3)如果|A|≤|B|，且|A| |B|，则称A的基数小于B的基数，记为|A|<|B|。

14 第六章 集合的基数 (1)对任意自然数m≤n，则|{0,1,2, …,m-1}| ≤ |{0,1,2, …,n-1}|;
(2)对以上自然数n, n< ，即|{0,1,2, …,n-1}| ≤|{0,1,2, …}|; (3) <c，即|{0,1,2, …}|<|R|; (4)是否存在无限集B，使得 <|B|<c，至今尚解决的理论问题。 定理6.12：对任意集合A，B，C有(1)|A|≤|A|；(2)|A|≤|B|，|B|≤|C|，则|A|≤|C|。 定理6.13：对任意集合A，B，或者|A|<|B|，或者|A|=|B|，或者|B|<|A|，且任意两者都 不能兼而有之。

15 第六章 集合的基数 定理6.14：对任意集合A，B，若|A|≤|B|，|B| ≤|A|，则|A|=|B|。
证：设|A| |B|，则或|A|<|B|，或|B|<|A|且不能兼而有之，而|A|≤|B|，|B| ≤|A|，矛盾。 例：P(N)(N为自然数集)额为连续统。 证：建立单射f:P(N)→[0,1]和单射g:[0,1]→P(N)即可。 定义f:P(N)→[0,1]。如下：

16 第六章 集合的基数 定义g:[0,1]→P(N)。如下： 对每一[0,1]中数的二进制表示(如果这种表示不唯一，则取定其中之一)。
定理6.15：(康托定理)设M为任意集合，记M的幂集为S，则|M|<|S|。 证：对任意集合M，当M= 时，显然|M|=0， |S|=1，成立； 当 时，对 ，因此如下函数f:M→S明显为一单射，即对每个 ，所以|M|<|S|；

17 第六章 集合的基数 现证明|M| |S|，用反证法。 设|M|=|S|，故有双射g:M→S，使得对每一个 有唯一的 ，定义集合：
当然 由于g为双射，对 ，有唯一的 ，使得g(y)=B，而 矛盾。 ∴g不存在，即|M| |S|， ∴ |M|<|S| 定理说明：没有最大的基数，也没有最大的集合。