离散数学第四章第二节

1、1第4-2讲 集合的基数1. 自然数集合2. 等势3. 可数集4. 不可数集5. 基数的比较6. 第4-2讲 作业21、自然数集合（1） 有时有时我们会对集合中元素的个数感兴趣，利用映射可我们会对集合中元素的个数感兴趣，利用映射可以研究这一问题。为此以研究这一问题。为此, 要用到自然数集合，它可由空要用到自然数集合，它可由空集及其后继集合的概念来产生。集及其后继集合的概念来产生。 若若A=A= ，则可产生下列后继集序列：，则可产生下列后继集序列： ， + +，( ( + +) )+ + ，( + +) )+ + )+，按按后继集定义，该序列就是：后继集定义，该序列就是： ， ， ， 可化简为：

2、可化简为： ， ， ， ， ， ， , 定义1 给定集合A，其后继集定义为集合： A+=AA31、自然数集合（2） 为书写方便，记空集为为书写方便，记空集为0 0，并且用，并且用1 1，2 2，3 3，表示序列表示序列 ， ， ， ， ， ， , ，中的其它元素，就得到序列：中的其它元素，就得到序列： 0，1，2，3， 这里的这里的0 0、1 1、2 2、3 3不过是集合的代号而已，完全可用任何不过是集合的代号而已，完全可用任何其它的符号取代。详细的说就是：其它的符号取代。详细的说就是： 0 = 0 = 1 = 0 1 = 0+ + = = = 0 2 = 12 = 1+ + = = ， =

3、0，1 3 = 2 3 = 2+ + = = ， ， , = 0，1，2 n+1= n+ = 0，1，2，3，n 如此可得如此可得“自然数集自然数集”：N=0N=0，1 1，2 2，3 3， ，它是集合的集合！它是集合的集合！41、自然数集合（3）自然数集自然数集N可用皮亚诺公理来概括：可用皮亚诺公理来概括： 1. 0 N; 2. 对每个对每个n N,恰有唯一的恰有唯一的n+ N; 3. 不存在不存在n N,使得使得n+=0; 4. 如果如果n+= m+,则则n=m; 5. 如果如果S N;且且0 S;同时同时,若若n S,则则n+ S；那么；那么S=N。l 皮亚诺公理使自然数具有如下结构皮亚

4、诺公理使自然数具有如下结构: :l 而排除了而排除了左面结构的左面结构的可能：可能：52、等势（1）定义3 当且仅当集合A、B元素之间存在一一对应，称集合A与B是等势的，或者说集合A、B有相同的基数，记作AB。集合A的基数记作KA。定义2 给定两个集合P与Q，如果存在双射f:PQ，则称集合P和Q的元素之间存在一一对应。 例如，自然数集例如，自然数集N与非负偶数集与非负偶数集M是等势的。因为存在双射是等势的。因为存在双射 f:NM，f(n)=2n。例1 设设R为实数集，为实数集，S=x|x R 0 x1，证明，证明SR。证：作映射：作映射f:RS,f(x)=(1/ )arctgx+1/2,显然，

5、显然，f是双射。是双射。62、等势（2）证：设设集合集合A A S，则，则AA，故，故是自反的。是自反的。 设设集合集合A A、B B S，如果，如果AB，则存在双射，则存在双射f:AB，因，因而而fC是是B到到A的双射，所以的双射，所以BA。故故是对称的。是对称的。 设设集合集合A A、B B、C C S，如果，如果AB，BC,则存在双射则存在双射f:AB，g:BC,因而因而g f是是A到到C的双射，所以的双射，所以AC。故故是传递的。是传递的。 综上述，等势关系综上述，等势关系是等价关系。是等价关系。定理2 设集合S的元素为集合(称S为集合族)，则S上的等势关系是等价关系。 等价关系等价关

6、系导出集合导出集合S的一个划分，这个划分的等价类的一个划分，这个划分的等价类叫基数类。属于同一基数类的集合有相同的基数，称它叫基数类。属于同一基数类的集合有相同的基数，称它们们“同基同基”。72、等势（3）定理3 自然数集N是无限集。证明：只须证集合只须证集合N N与集合与集合N Nm m不等势。即证不等势。即证不不存在存在N Nm m到到N N的的双射。双射。 假设存在双射假设存在双射f:Nf:Nm mN N， 令令k=1+maxf(0), f(1),k=1+maxf(0), f(1),f(m),f(m)，则，则k k N N。但。但 x x N Nm m，f(x)f(x) k k，所以，所

7、以f f不可能是满射，更不能是双射。不可能是满射，更不能是双射。这说明不这说明不存在存在N Nm m到到N N的的双射，从而双射，从而N N不是有限的。不是有限的。定义4 令令Nm=0,1,2,3,m ，如果集合A与Nm等势，则称A为有限集，否则A称为无限集。83、可数集（1） 自然数集是无限的，但是否所有的无限集都能与自然数自然数集是无限的，但是否所有的无限集都能与自然数集建立一一对应呢？集建立一一对应呢？定 理 4 集 合 A 是 可 数 集 当 且 仅 当 A 可 写 成a1,a2,.,an,.。定义5 与自然数集N等势的集合称为可数集(可列集)，可数集的基数用符号 表示，读作阿列夫零。

8、证：若若A可写为可写为a1,a2,.,an,.。可作双射可作双射f:Nf:NA A，f(n)=af(n)=an n，按定义，按定义，A A是可数集。是可数集。 反之，若反之，若A A是可数集，那么，是可数集，那么，A A与与N N存在一一对应关系存在一一对应关系：f:Nf:NA A，可令，可令f(n)=af(n)=an n(n(n N)N)，于是，于是A A可写成可写成aa1 1, , a a2 2, ., a, ., an n,. ,. 。93、可数集（2）定理5 任一无限集 必含有可数子集。定理6 任一无限集必与它的一个真子集等势。 证：设设A A为无限集，可取为无限集，可取a1 A A；

9、因；因A A是无限的，所以是无限的，所以A-A-a1 仍为无限仍为无限集，再取集，再取a2 A A-a1 ；同样；同样A-A-a1 ,a2 仍为无限集，再取仍为无限集，再取a3 A A- - a1 ,a2 ；如此继续，就得如此继续，就得A的一个可数子集的一个可数子集 a1，a2，a3， 。证：设设M为为无限集无限集，按定理5，M含可数子集可数子集A=A=aa1 1, a, a2 2, ., .。令。令B=M-AB=M-A，那么，那么M=BM=B A=BA=B aa1 1, a, a2 2, ., .。 记记M=M=B B aa2 2, a, a4 4, ., .。它是。它是M M的一个真子集。

10、可作双射的一个真子集。可作双射f:Mf:MM M，使，使: :Bxxxfiaafii)(,.3 , 2 , 1)(2 所以所以MM。103、可数集（3）定理7 可数集的任一无限子集是可数的。 （证明从略）定理8 可数个可数集的并是可数集。 （证明从略）定理9 NN是可数集(N为自然数集)。 （证明从略）定理10 全体有理数的集合是可数集。 可按下列规则将全体有理数排成一列：可按下列规则将全体有理数排成一列： 1、正分数按分子分母之和从小到大排列；、正分数按分子分母之和从小到大排列； 2、正分数分子分母之和相同时，按分子的大小由小到大排列；、正分数分子分母之和相同时，按分子的大小由小到大排列；

11、3、与正分数分子分母对应相同的负分数排在相应的正分数之后。、与正分数分子分母对应相同的负分数排在相应的正分数之后。 0，1/1，-1/1，1/2，-1/2，2/1，-2/1，1/3，-1/3，3/1，-3/1，1/4，-1/4，2/3，-2/3，3/2，-3/2，4/1，-4/1，.114、不可数集（1）定理11 实数集R是不可数的。 证明：先证集合先证集合S=x|xS=x|x R R (0 x1)(0 x1) 与与R R等势。等势。为此，作双射为此，作双射f:Sf:SR,R,12/11) 1(212/10121)(xxxxxf其次，用反证法证其次，用反证法证S是不可数的，从而是不可数的，从而

12、R不可数。不可数。 假设假设S S可数，则可数，则S S可表示为可表示为SS1 1，S S2 2，.，其中，其中S Si i 为为(0,1)(0,1)内的内的任一实数，可表示为任一实数，可表示为0.y0.y1 1 y y2 2 y y3 3, ,其中其中y yi i 0,1,2,0,1,2,9,9。可设可设 S S1 1= = 0.a 0.a11 11 a a12 12 a a1313a a1n1n ； . .S S2 2= = 0.a 0.a21 21 a a22 22 a a2323a a2n2n S S3 3= = 0.a 0.a31 31 a a32 32 a a3333a a3n3n

13、 ； 令令r=0.br=0.b1 1b b2 2b b3 3，其中，其中b bi i=1(a=1(aiiii 1)1)或或b bi i=2(a=2(aiiii=1)=1)，i=1,2,3,i=1,2,3,显然显然r r S S，但由上所设，这个，但由上所设，这个r r与所有的与所有的S Si i都不同，因而都不同，因而r r S S，与所，与所设矛盾。故设矛盾。故S S是不可数的，所以是不可数的，所以R R也是不可数的。也是不可数的。124、不可数集（2） 将实数集R的基数记为 ，称为连续统的势。直观上看，自然数集N是实数集R的子集，那么， 。135、基数的比较（1）定义6 设A、B为集合，如

14、果存在A到B的入射，则称A的基数小于或等于B的基数，记作KAKB。如果存在A到B的入射，但不存在双射，则称A的基数小于B的基数，记作KAKB。 无限集合也有无限集合也有“大小大小”之分，下面的定义提供了无之分，下面的定义提供了无限集合比较的基础。限集合比较的基础。定理12 (Zermelo定理) 设A、B为任意两个集合，则下列三者恰有一个成立： (1) KAKB；(2) KBKA；(3) KA=KB。定理13 (Bernstein定理)设A、B为集合,如果KAKB,KBKA，则KA=KB。 按定义按定义6 6和定理和定理13,13,如果能作出如果能作出A A到到B B和和B B到到A A两个入

15、射两个入射, ,就可就可证明证明集集合合A A与与B B的基数相同。这比直接作的基数相同。这比直接作A A到到B B的双射来证明要容易些。的双射来证明要容易些。145、基数的比较（2）定理14 设A为有限集合，KA 。证明：设设KA=n，则A0，1，2，n-1。可作入射 f： 0,1,2,n-1N ， f(x)=x 所以，KA KN。 显然A到N不可能存在双射，故KA KN，所以KA KN，即 KA 。 作入射g：N0，1，g(n)=1/(n+1)。可知 。 因0，1是不可数集，所以N与0,1之间不能建立一一对应，故 155、基数的比较（3）定理15 (Cantor定理) 设M为集合，则KMK

16、(M)。(证明从略)l定理定理15说明，没有最大的集合，也没有最大的基数。说明，没有最大的集合，也没有最大的基数。lCantor(1845-1918)早在早在100多年前提出一个猜想：多年前提出一个猜想： 是大于是大于 的最小基数。即不存在任何集合的最小基数。即不存在任何集合X，它的基数，它的基数KX能使能使 KX 成立。这个问题是近百年来数理逻成立。这个问题是近百年来数理逻辑的中心问题之一，也是集合论中最难的问题之一。它至辑的中心问题之一，也是集合论中最难的问题之一。它至今仍然没有得到证明。今仍然没有得到证明。165、课堂练习练习1 证明 0，1与（0，1）表示的集合有相同的基数。证： 作入射：作入射： f:(0,1)f:(0,1)0,1,f(x)=x0,1,f(x)=x g:0,1g:0,1(0,1)(0,1)，g(x)=g(x)=( (x+1)/4x+1)/4 根据根据定义定义6 6和和定理定理1313, 0, 0，11与（与（0 0，1 1）表示的集合有）表示的集合有相同的基数。相同的基数。练习2 （P173，1）证明证明(0,1(0,1与与0