离散数学课件：4-6 基数的比较

1、 为了证明两个集合的基数相等，我们必须构为了证明两个集合的基数相等，我们必须构造两个集合之间的双射函数，这常常是非常困难造两个集合之间的双射函数，这常常是非常困难的工作。本节将介绍证明基数相等的一个较为简的工作。本节将介绍证明基数相等的一个较为简单的方法，但是简单方法的证明是冗长和复杂的，单的方法，但是简单方法的证明是冗长和复杂的，因而我们只给出结论不予证明。为此首先说明基因而我们只给出结论不予证明。为此首先说明基数是如何比较大小的。数是如何比较大小的。定理定理1:设设A, B, C是任意集合是任意集合, 那么那么(1)若若A B, 则则KA KB;(2)若若KA KB, KB KC, 则则K

2、A KC.定义定义1:若从集合若从集合A到集合到集合B存在一个入射，则称存在一个入射，则称A的基数不大于的基数不大于B的基数，记作的基数，记作 KA KB. 若从若从A到到B存在一个入射，但不存在双射，则称存在一个入射，但不存在双射，则称A的基的基数小于数小于B的基数，记作的基数，记作KAKB.六、基数的比较六、基数的比较Zermelo定理定理定理定理2: (Zermelo定理或称三岐性定理定理或称三岐性定理) 令令A和和B是任意集合，则以下三条中恰有一条是任意集合，则以下三条中恰有一条成立：成立：a)KAKB;c)KA=KB. 六、基数的比较六、基数的比较Cantor-Schroder-Be

3、rnstein定理定理定理定理3: (Cantor-Schroder-Bernstein定理定理) 设设A和和B是任意集合，若是任意集合，若KA KB, KB KA, 则则KA=KB. F若存在从若存在从A到到B和和B到到A的入射函数，则存在从的入射函数，则存在从A到到B的双射函数。的双射函数。F它为证明两个集合具有相同的基数提供了有效它为证明两个集合具有相同的基数提供了有效方法。这是因为构造两个入射函数比构造一个双方法。这是因为构造两个入射函数比构造一个双射函数要容易得多。射函数要容易得多。六、基数的比较六、基数的比较证明证明0,1与与(0,1)有相同的基数。有相同的基数。证：证：因为可作入

4、射因为可作入射f :(0,1)0,1, f(x)=x, 故故K(0,1) K0,1;又可作入射又可作入射g:0,1(0,1), g(x)=x/2+1/4, 故故K0,1 K(0,1).由定理由定理3可得，可得，K0,1=K(0,1). F此两函数的选取方法不唯一，如也可取此两函数的选取方法不唯一，如也可取f (x) =x/2, g(x) =x/3+1/3.六、基数的比较六、基数的比较设设A=N, B=(0,1), KA=0, KB =, 求证：求证：KA B=.证：证：因为可作入射因为可作入射f :A BR, f(n,x)=n+x, 故故KA B KR= ;又可作入射又可作入射g:(0,1)

5、A B, g(x)=, 故故=K(0,1) KA B.因此，因此，KA B= .六、基数的比较六、基数的比较 又因为又因为N为可数集为可数集, (0,1)为为不可数集，故不可数集，故N与与 (0,1) 之间不存在双射函数之间不存在双射函数 , 又因为在又因为在4-4节节中证明中证明N是无限集时已证明是无限集时已证明N与与A之间不存在之间不存在双射函数，双射函数， 因可定义入射函数因可定义入射函数 f : NnN, f (x)=x, 定理定理4: 设设A是有限集合，则是有限集合，则KA0.证：证：设设KA=n, 则则ANn, 故故KA KN.所以所以KA KN.故故KAKN= 0. 再因可定义入

6、射函数再因可定义入射函数 g : N0, 1, g(n)=1/(n+1), 故故0 .所以所以0.F此定理指出了此定理指出了有限集基数、可数集基数和连续有限集基数、可数集基数和连续统的势之间的关系。统的势之间的关系。六、基数的比较六、基数的比较定理定理5:如果如果A是无限集，那么是无限集，那么0 KA.证：证： 因为因为 A 为无限集，为无限集， 由由4-5节的定理节的定理2知知A必含必含有一个可数无限子集有一个可数无限子集 B. 因为可作入射函数因为可作入射函数 f : BA, 使得使得 f (x) = x. 故故KA KB=0.F0是无限集中最小的基数。是无限集中最小的基数。F如果如果 A

7、 为无限集，那么为无限集，那么0 KA, 0.德国德国数学家康托尔认为数学家康托尔认为0与与之间没有其他基数存之间没有其他基数存在，这就是著名的在，这就是著名的连续统假设连续统假设。但是到目前为。但是到目前为止还没有人能够证明它。止还没有人能够证明它。六、基数的比较六、基数的比较定理定理5: (Cantor定理定理)设设A是任意集合，是任意集合，T=P(A), 则则KAKT.证：证：a)首先证明首先证明KA KT.问题：问题：是否存在基数大于是否存在基数大于的集合的集合?是否有最大是否有最大基数的集合基数的集合?故故KA KT .因为可作入射函数因为可作入射函数 f : AT, f (a)=a

8、,六、基数的比较六、基数的比较 则有则有S A, 记记S=x|x A,x (x), 即即S为为A的外部元素集合，的外部元素集合，定理定理5: (Cantor定理定理)设设A是任意集合，是任意集合，T=P(A), 则则KAKT.证证(续续)： b)其次证明其次证明KA KT. 用反证法证明。用反证法证明。假设假设KA=KT, 则必存在双射函数则必存在双射函数 : AT , 从而对从而对于于任意任意a A, 存在唯一的存在唯一的 (a) T 与之对应，即与之对应，即a (a). 若若a (a), 则称则称a为为A的内部元素，若的内部元素，若a (a), 则称则称a 为为A的外部元素。的外部元素。故

9、故S T. 因为因为 是双射函数，故必有一个元素是双射函数，故必有一个元素b A, 使使 (b)=S.故故KA KT. 由由a), b)可得，故可得，故KAKT. (1)若若b S, 则则b ( (b) ). 由由 ( (b)=)=S 可得可得b S, 矛盾。矛盾。(2)若若b S, 则则b (b). 由由 (b)= =S 可得可得b S, 矛盾。矛盾。六、基数的比较六、基数的比较六、基数的比较六、基数的比较定理定理6: 设设N为自然数集，则为自然数集，则KP(N)=.证：证： 构造函数构造函数f: 0,1P(N), 使得对任意的使得对任意的x=.x0 x1x2 0,1, 有有f(x)=j|x

10、j=1.其中其中.x0 x1x2为为x的二进制表示。的二进制表示。例如，例如，f(0)=f(1)= .111=Nf(.1010100)= 0,2,4.显然，显然，f是双射，是双射，从而从而0,1P(N), 所以所以KP(N)= K0, 1=.1: 线段上所有几何点的个数，或实数的个数；线段上所有几何点的个数，或实数的个数；0: 现在我们对有限集的基数计数：现在我们对有限集的基数计数：0,1,2,3,对无限集的计数对无限集的计数: 0, KP(N)= 1, KP(P(N) 2, 与现实生活能对应的：与现实生活能对应的：2: 所有整数或分数的个数；所有整数或分数的个数；所有几何曲线的个数。所有几何

11、曲线的个数。 到现在为止，对于比到现在为止，对于比2大的有实际意义的大的有实际意义的无限集还没有发现。无限集还没有发现。实际意义实际意义六、基数的比较六、基数的比较 所以可作入射函数所以可作入射函数 f: (0, 1)(0, 1)N设设A、B、D是任意集合是任意集合且且AB=AD=BD=, KA=a, KB=b, KD=d, 若定义若定义a+b=KAB, a b=KA B.求证求证：(a) +0=; (b) 如果如果a b, 则则a+d b+d; (c) 如果如果a b, 则则ad bd.证：证：(a)设设KA= , KB=0, 则则 A(0, 1), BN,注意到注意到AB= , (0, 1

12、)N= ,由由4-4习题的习题的(3)知知AB (0, 1)N因为因为(0, 1) (0, 1)N, 所以所以KAB=K(0, 1)N.从而从而K(0, 1)N K(0, 1)= . 同理可证同理可证K(0, 1)N KR= , 所以所以K(0, 1)N= .综上，综上， +0= K(0, 1)NKA+KB= KAB= .六、基数的比较六、基数的比较设设A、B、D是任意集合是任意集合且且AB=AD=BD=, KA=a, KB=b, KD=d, 若定义若定义a+b=KAB, a b=KA B.求证求证：(a) +0=; (b) 如果如果a b, 则则a+d b+d; (c) 如果如果a b, 则

13、则ad bd.证（续）：证（续）：(b) 因为因为a b, 所以必存在一个入射函数所以必存在一个入射函数f: AB.从而可定义入射函数从而可定义入射函数g: ADBD, 使使g(x)=f(x),x Ax,x D故故KAD KBD.由于由于AD=BD=, 故得故得a+d b+d.六、基数的比较六、基数的比较设设A、B、D是任意集合是任意集合且且AB=AD=BD=, KA=a, KB=b, KD=d, 若定义若定义a+b=KAB, a b=KA B.求证求证：(a) +0=; (b) 如果如果a b, 则则a+d b+d; (c) 如果如果a b, 则则ad bd.证（续）：证（续）：(c) 因为因为a