第六章集合的基数 在前面我们的基数简单的看作集合元素的个数，这 对于有限集来说没有问题，但对于无限集而言， 元素的个数”这个概念是没有意义的，那么两 个集合的“大小”，“相同”的确切含义是什么 呢？形式的描述元素“多少”的概念数学工具是 函数。 先讨论自然数集合，有限集，无限集。 173
1/73 第六章 集合的基数 在前面我们的基数简单的看作集合元素的个数，这 对于有限集来说没有问题，但对于无限集而言， “元素的个数”这个概念是没有意义的，那么两 个集合的“大小”，“相同”的确切含义是什么 呢？形式的描述元素“多少”的概念数学工具是 函数。 先讨论自然数集合，有限集，无限集
第六章集合的基数 定义6.1：设S为任意集合，SU{S}称为S的后继集 合，记为S+,显然S∈，S∈S+。 例：令S=0,则0可以构造出集合序列： 00 10U0} 2{0}U{{0}}={0,{0}} 将上面的集合依次命名为0,1,2，"， 就可构造出自 然数，用：=”来命名；即 0:=0,1=0*={0}={0},2:=1*={0,{0}}={0,1} 3=2*={0,{0},{0,{0}}}={0,1,2 一般地：n+1=n*={0,12,…} 自然数集N{0,1,2,} 2/73
2/73 第六章 集合的基数 • 定义6.1：设S为任意集合，S∪{S}称为S的后继集 合，记为 ，显然 。 例：令 ，则 可以构造出集合序列： 将上面的集合依次命名为0,1,2， …，就可构造出自 然数，用“:=”来命名；即 一般地： 自然数集N={0,1,2， …} + S + + S S , S S S = 2 { } {{ }} { ,{ }} 1 { } 0 = 3: 2 { ,{ },{ ,{ }}} {0,1,2} 0: ,1: 0 { } {0},2: 1 { ,{ }} {0,1} = = = = = = = = = = + + + +1:= ={0,1,2, } + n n
第六章集合的基数 G.Peano将自然数所组成的集合的基本特征描述为 下列公理；设N表示自然数集合，则 (1)0记为0,0∈N,(2)若n∈N,则n∈W (2),若子集S∈N且0∈S,又若n∈S,则n*∈S,则S=N 其中(3)说明了N是满足条件(1)，(2)的最小集合， (3)也称为极小性质 。 ·定义6.2：如存在集合{0,1,2， …,-1}（自然数 n)到A或A到集合{0,1,2，· ",n-1}的双射，则集 合A称为有限集，否则称为无限集。 ·定理6.1：自然数集为无限集。 373
3/73 第六章 集合的基数 • G•Peano将自然数所组成的集合的基本特征描述为 下列公理；设N表示自然数集合，则 其中(3)说明了N是满足条件(1)，(2)的最小集合， (3)也称为极小性质。 • 定义6.2：如存在集合{0,1,2， … ，n-1}(自然数 n)到A或A到集合{0,1,2， … ，n-1}的双射，则集 合A称为有限集，否则称为无限集。 • 定理6.1：自然数集N为无限集。 S N S n S n S S N N n N n N = + + 若子集 且 ，又若 则 则 记为 若 则 (2), 0 , , (1) 0,0 ,(2)
第六章集合的基数 证明：只要证明N不是有限集，反证法。 设N为有限集，即存在f是[0,1,2，"，n-1}到N的双 射，现令L∈N,L=1+max{f(0),f(I),…,f(n-1)},显 然对i=0,1,…,-1,恒有f(i)<L,这就是说f不是 满射，矛盾。∴不是有限集，是无限集 定理6.2：有限集的任何子集均为有限集。 证明：设S为有限集，因而有双射f,自然数n,f: {0,1,…,n-1}→S,因此S={f(0),f(1),",f(n 1)],若S,为S的任一子集，则S,={f(ao),,f(ak-)} k≤n,a,a1,…ak-1为{0,1,2，…，n-1}中的不同成 员将序列，4，…ak-1看作{0,1,2，…，k-1}到 {ao,a41,…ak-1}=S2的双射，记为g, 4/73
4/73 第六章 集合的基数 证明：只要证明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， L N, L =1+ max{ f (0), f (1), , f (n −1)} S1 { ( ), , ( )} 1 = 0 ak−1 S f a f 0 1 1 , , , n a a ak− k 0 1 1 , , a a ak− 0 1 1 2 {a ,a , ak− }= S
第六章集合的基数 那么：8of:0,12,…,k-1}→S,为双射，因此，A 为有限集。 ·定理6.3：任何含有无限子集的集合必定是无限集 此定理是6.2的逆否命题，所以也成立。 理6.4：无限集必与它的一个真子集存在双射函 数 证明：设S为任一无限集，显然S≠D 可取元素a∈S 考虑S,=S-{a},S仍为非空无限集，又在S中 可取4∈S1,考虑S2.=S-{a,S2仍为非空无限集 同样有a2∈S2,…令B={a,a4,a,显然BcS 且对任-自然数n,总有an∈B,令S。=S-{a,}cS 定义函数f:S→S为： 5/73
5/73 第六章 集合的基数 那么： 为双射，因此，A 为有限集。 • 定理6.3：任何含有无限子集的集合必定是无限集 此定理是6.2的逆否命题，所以也成立。 • 定理6.4：无限集必与它的一个真子集存在双射函 数。 证明：设S为任一无限集，显然 ，可取元素 ，考虑 ， 仍为非空无限集，又在 中 可取 ，考虑 ， 仍为非空无限集 ，同样有 令 ，显然 ，且对任一自然数n，总有 ，令 定义函数 为： 1 g f :{0,1,2, ,k −1}→S S a0 S { } S1 = S − a0 S1 S1 a1 S1 { } S2 = S1 − a1 S2 a2 S2 , { , , , } B = a0 a1 a2 B S an B S0 = S −{a0 } S 0 f : S → S
第六章集合的基数 xB f(x)= x=a∈B(i=0,l,…) 易知f为一双射，.命题成立。 推论：凡不能与自身的任意真子集之间存在双射 函数的集合为有限集合。 定义6.3：如果存在从N到S的双射，则称集合S为 可数无限集(Conntable Infinite Sets).。其它无 限集称为不可数无限集。有限集合和可数无限集 统称为可数集（不可数集即不可数无限集） 显然，N是可数集，可以排成一个无穷序列的形式 :0,1,2,因此，其它任何可数集合S中的元素 也可以排成一个无穷序列a4,4,…,an,… 6/73
6/73 第六章 集合的基数 易知f为一双射，∴命题成立。 • 推论：凡不能与自身的任意真子集之间存在双射 函数的集合为有限集合。 • 定义6.3：如果存在从N到S的双射，则称集合S为 可数无限集(Conntable Infinite Sets)。其它无 限集称为不可数无限集。有限集合和可数无限集 统称为可数集(不可数集即不可数无限集)。 显然，N是可数集，N可以排成一个无穷序列的形式 ：0,1,2， …因此，其它任何可数集合S中的元素 也可以排成一个无穷序列 = = = + ( 0,1, ) ( ) a 1 x a B i x x B f x i i a0 ,a1 , ,an ,
第六章集合的基数 一个集合是可数集的充要条件是它的元素可以排成 一个无穷序列的形式。 ·定理6.5：整数集为可数无限集。 证：建函数：f:Z→N: 2x x>0 f(x)={0 x=0 2(-x)-1x<0 易知f(x)为一双射，.Z为可数集。 ·定理6.6：任何无限集必有一个可数子集。 证：类似于6.4，从无限集中依次取出一列元素，构 成一个可数集。 773
7/73 第六章 集合的基数 一个集合是可数集的充要条件是它的元素可以排成 一个无穷序列的形式。 • 定理6.5：整数集为可数无限集。 证：建函数：f:Z→N： 易知f(x)为一双射，∴Z为可数集。 • 定理6.6：任何无限集必有一个可数子集。 证：类似于6.4，从无限集中依次取出一列元素，构 成一个可数集。 − − = = 2( ) 1 0 0 0 2 0 ( ) x x x x x f x
第六章集合的基数 •定理6.7：可数集的任何无限子集必为可数集 证：设S是可数集，S中的元素可以排成：4o,4,a2, 设B是S的任一无限子集，它的元素也是S的元素 并且它可排成：ak,4k,4k,,∴.B是可数集。 ● 定理6.8：可数集中加入有限个元素（或删除有限 个元素)仍为可数集。 证：设S={a,a,是可数集，不妨在S中加入有限个 元素b,b,…,b,且它们均与S的元素不相同，得 到新的集合B,它的元素也可排成无穷序列： b,b1,…,bnm,40,41,…∴.B是可数集。 8/73
8/73 第六章 集合的基数 •定理6.7：可数集的任何无限子集必为可数集。 证：设S是可数集，S中的元素可以排成： ，设B是S的任一无限子集，它的元素也是S的元素 ，并且它可排成： ，∴B是可数集。 • 定理6.8：可数集中加入有限个元素(或删除有限 个元素)仍为可数集。 证：设 是可数集，不妨在S中加入有限个 元素 ，且它们均与S的元素不相同，得 到新的集合B，它的元素也可排成无穷序列： ∴B是可数集。 a0 ,a1 ,a2 , a0k ,a1k ,a2k , { , , } S = a0 a1 b b bm , , , 0 1 b0 ,b1 , ,bm ,a0 ,a1 ,
第六章集合的基数 •定理6.9：两个可数集的并集是可数集。 证：设S1={a0,41,a2,},S2={b,b,b2,}均为可数集 不妨设S和S2不相交，SUS2元素可以排成无穷序 列：a,b,a4,b,…SUS2为可数集。 ·推论：有限个可数集的并是可数集 。 ● 定理6.10：可数个可数集的并集是可数集。 证：不失一般性，设这可数个可数集均非空，且互 不相交 S0={a0,a4o1,a2,} S1={a10,a1,a12,} S2={a20,a21,a2,…} 9/73
9/73 第六章 集合的基数 •定理6.9：两个可数集的并集是可数集。 证：设 均为可数集， 不妨设 不相交， 元素可以排成无穷序 列： 为可数集。 • 推论：有限个可数集的并是可数集。 • 定理6.10：可数个可数集的并集是可数集。 证：不失一般性，设这可数个可数集均非空，且互 不相交： { , , , }, { , , , } S1 = a0 a1 a2 S2 = b0 b1 b2 S1 和S2 S1 S2 0 0 1 1 1 2 a ,b ,a ,b , S S { , , , } { , , , } { , , , } 2 2 0 2 1 2 2 1 1 0 1 1 1 2 0 0 0 0 1 0 2 S a a a S a a a S a a a = = =
第六章集合的基数 当S,为有限集{a,0,a1,…,ak时，令ak=ak+l=ak+2)=… 从而S=US=S。US US,U.…,S中元素排列为： a0,a1,410,42,411,420,…∴.S为可数集 。 >NXN是可数集；有理数是可数集（证明见书）。 ·定理6.11：实数集的子集[0,1]区间是不可数集。 证：用反证法。设[0,1]为可数集{a,a,a2,}，由 于[0，]中的实数均可表示为十进制无限小数，因 此0,1j中的实数可如下列出：a:0.xoo1x2… a1:0.X10X11X12 10/73
10/73 第六章 集合的基数 当 为有限集 时，令 从而 ，S中元素排列为： ∴S为可数集。 ➢N×N是可数集；有理数是可数集(证明见书)。 • 定理6.11：实数集的子集[0,1]区间是不可数集。 证：用反证法。设[0,1]为可数集 ，由 于[0,1]中的实数均可表示为十进制无限小数，因 此[0,1]中的实数可如下列出： Si { , , , } ai0 ai1 aik ai k = ai(k+1) = ai(k+2) = S = Si = S0 S1 S2 a00,a01,a10,a02,a11,a20, { , , , } a0 a1 a2 0 1 2 1 1 0 1 1 1 2 0 0 0 0 1 0 2 : 0. : 0. : 0. n n n n a x x x a x x x a x x x