离散数学高等里离散数学-课件-CHAP4

1、2020/9/4,离散数学,1,第四章 可数集与不可数集,2020/9/4,离散数学,2,4.1 等势,如何比较两个集合中元素的多少呢？,2020/9/4,离散数学,3,等势,定义4.1.1：设A和B是集合，若存在A到B的双射，则称A与B等势，记为A B .(可形象理解为A与B的元素一样多。) “”是一个等价关系。(请证之?) 例1 自然数集N与偶自然数集E是等势的，其中定义N到E的双射为： (n) = 2n , nN.,2020/9/4,离散数学,4,有限与无限,定义4.1.2：设Nn=0,1, , n 1 , n1 ,若集合A与Nn等势，则称A为有限集；否则称A为无限集。,2020/9/4

2、,离散数学,5,无限多的自然数,定理4.1.1 自然数集合N是无限集。 证明：设nN，n 1 , 令是从Nn到N的映射，Nn=0,1, , n1 ，下证不是双射。 令k=1+max(0), (1), , (n1) , 于是kN，但对任意xNn ,均有(x) k , 因此，不是满射，更不是双射。由定义知，N为无限集。,啊哈！这下我们知道有无限多个自然数了！,2020/9/4,离散数学,6,抽屉原理,定理4.1.2 任何有限集均不能和其真子集等势 此定理也称为抽屉原则：若将n+1个物体放入n个抽屉中，则至少有一个抽屉中放了两个或两个以上的物体。 抽屉原则对无限集并不总是成立，即无限集能够与其真子集

3、等势。这是无限集合的一个非常重要的性质。 我们已经看到自然数集合等势于它的真子集，偶数集合。下面我们再给一个例子。,2020/9/4,离散数学,7,正实数和全体实数一样多,令R和R+分别为实数集合和正实数集合，即R+=xR | x 0 ，显然，R+ R ，即R+是R的真子集。但是RR+ 证明：定义映射 f 如下： f (x) = ex , xR 于是，对任意的xR，存在唯一的yR+ ,使 y = ex = f (x) ； 另一方面，对任意的yR+ ,存在唯一的 x =lnyR , 使 f (x) = ex = elny = y , 这说明 f 是R到R+的一个双射。因此， RR+ 。,2020

4、/9/4,离散数学,8,4.2 集合的基数,2020/9/4,离散数学,9,几个记号,同有限集合中元素的个数的记法一样，集合A的基数用 |A|表示。 每个有限集合都与某个集合Nn= 0,1, , n1等势，其中n 0 , N0 = 。如果A Nn , 则A中有n个元素，即|A| = n; 若A为无限集，则用一个特殊的符号i(读作阿列夫i，i是一个正整数)来表示它的基数。例如，对于自然数集合N，令|N| = 0 ( 读作 “ 阿列夫零 ” ) 。,2020/9/4,离散数学,10,如何比较集合的大小,(1)若AB ,即存在A到B的双射，则称它们的基数相等, 记为|A|=|B|。 (2)若存在A到

5、B的单射，则称A的基数小于或等于B的基数，记为|A| |B|；或称A的基数大于或等于B的基数，记为|B| |A|。 (3)若两者基数不等且|A|B|，则记为|A| |B|。,根据集合的基数来比较它们的大小。令A、B为两个集合，则：,2020/9/4,离散数学,11,集合大小是可比的,定理4.2.1 设A和B为两个集合，总有 |A| |B|或者|B| |A| 。(即任意两个集合总可比较大小。）,像实数一样，任何两个基数都可以比较大小，所以有,2020/9/4,离散数学,12,等势是集合间的等价关系,定理4.2.2： 基数之间的相等关系“= ”是一个等价关系,即对任何集合A , B和C, 有: (

6、1)|A|=|A|; (2)若|A|=|B| ,则 |B|=|A|; (3)若|A|=|B|且|B|=|C| , 则|A|=|C| .,2020/9/4,离散数学,13,基数间的是偏序关系,定理4.2.3 基数之间的小于或等于关系“ ”是一个偏序关系,即对任何集合A , B和C, 有: (1)|A| |A|; (2)若|A| |B|且|B| |A| ,则 |A|=|B|; (3)若|A| |B|且|B| |C| , 则|A| |C| .,2020/9/4,离散数学,14,几个关于基数的问题,我们知道自然数有无限多个。那么自然数集合是不是就是最大集合的呢？ 如果自然数集合不是最大的，那么比它更大

7、的集合是什么样的呢？ 是不是存在最大的基数呢？ 不！不存在最大的集合。山外有山，天外有天。我们的口号是：没有最大，只有更大 ！,2020/9/4,离散数学,15,山外青山楼外楼,定理4.2.4 对任意集合A,均有|A| | (A)| ,其中(A)为A的幂集。 证明： 令 f : A(A)。f (a) =a， aA。 显然，f 是单射,于是|A| |(A)| . 显然，象集 a | aA 是(A)的真子集，所以，f 不是满射，从而不是双射。于是我们有|A| |(A)|。,错！错！错！,错误是：虽然f不是双射，但不能说明A与 (A)之间不存在其它的映射是双射。 正确的作法是证明A与 (A)存在任何

8、的双射都是不可能的。,2020/9/4,离散数学,16,山外青山楼外楼,假设|A| = |(A)|，则存在A到(A)的双射g . 令B=aA | a g(a) (g(a)是a所对应的子集)，显然B(A)。bA,使g(b) =B 。但是 (1)若bB，则由B之定义有bg(b)，即bB ; (2)若bB，即bg(b)，则由B之定义有bB。 总之有bB当且仅当b B，矛盾。 故|A|(A)|。综合以上，定理得证。,定理4.2.4 对任意集合A,均有|A| | (A)| ,其中(A)为A的幂集。 证明： 令f ：A(A)。f (a) =a， aA。 显然，f 是单射，于是|A| |(A)| 。,202

9、0/9/4,离散数学,17,无限集也分大小，且无最大者,定理4.2.4说明：对任意无限集，它的幂集就比它大。因此对任意无限集都存在更大的集合。 我们记自然数集合N的幂集的基数为1，也就是| (N)| =1 ， 由定理4.2.4知， 0 1 。 可以证明 |R| = | (N)| , 其中R为实数集，于是， | N | |R|。实际上N是最小的无限集。 依次可以推得实数集合的幂集的基数为2，,2020/9/4,离散数学,18,4.3 可数集与不可数集,2020/9/4,离散数学,19,可数集,定义4.3.1：设A是一个集合，若A与N等势，则称A为可数无限集；若A是有限集，则称A为可数集。 有时也

10、将可数无限集简称为可数集。 不是可数集的集合就称为不可数集。,2020/9/4,离散数学,20,整数集是可数集,例1：整数集Z是可数集。 证明：可定义N到Z的映射如下： (n) =-n/2 (n为偶数） (n) =(1+n)/2 (n为奇数） 不难验证为双射,故NZ, 则Z是可数集。,2020/9/4,离散数学,21,定理4.3.1 A是可数无限集当且仅当A的所有元素可以如下编号排出： a1 , a2 , a3 , , an , 此定理告诉我们，任何集合只要它的元素可以排序，就是可数的。,可数集是可数的,2020/9/4,离散数学,22,可数集的子集仍是可数的,定理4.3.2 可数集的子集仍是

11、可数集。 证明：设A是可数集，若A是有限集，则它的子集仍是有限集，当然也是可数集。若A是无限集，则由定理4.3.1知，A的元素可排列成： a1 , a2 , a3 , , an , (3.3) 显然，A的无限子集可如下得到： 从左向右看式(3.3)，可以依据子集中元素出现的次序将该子集的元素排列为： aj1 , aj2 , aj3 , , ajn , 由定理4.3.1知，该子集是可数集。,2020/9/4,离散数学,23,有理数集Q是可数集。,例2：有理数集是可数集。 证明：已知任何非零有理数均可表示成确定的既约分数，故把全体有理数按如下方式排列： (1)0排在最前面； (2)对正分数，按它的

12、分子与分母的和数由小到大排列，若和数相等，则分子小的排前面； (3)对负分数，把它紧排在相应的正分数后面。 显然，任意有理数总会排入此序列中。由定理4.3.1知，Q是可数集。,这种排序的方法称为字典排序法。,2020/9/4,离散数学,24,三角形方法,有理数还可以按下表排序：,显然用此方法可将所有的有理数排序。,分子,分母,1 2 3 4 5 6 ,1 2 3 4 . . ., ,此方法称为三角形方法，是很有用的方法。,2020/9/4,离散数学,25,符号串的集合是可数的,令为一字母表， 上的符号串为+： + = 1 +2 +3 +4+=i i=1 这里i为长度为i的的符号串的集合。,+为

13、可数集。,事实上，若| = k， 则每一个符号串就是一个 k 进制的数，显然它们是可以按序排列起来。所以+为可数集。,2020/9/4,离散数学,26,不是所有的集合都能排序,如果一个集合的元素可以排序，那么我们就可以一个一个地去数。,是不是所有的集合的元素都能排序呢？,不！不是所有的集合都能排序。,比如0，1中实数的集合。让我们来设想一下将它的元素排一个序： 0理所当然排在第一位。 但是0之后应该排哪个呢？,0.1？不！,0.01？不！,0.001？不！,.？,你会发现第二个就不知道排哪个好了。,这样看来实数集合是没法去数了！,?,2020/9/4,离散数学,27,实数集是不可数的,定理4.

14、3.3：实数集是不可数的。 证明：取R的子集 (0,1)=xR | 0 x 1 ,由定理4.3.2知，只需证明(0,1)是不可数集即可。 若(0,1)可数，则可将(0,1)中的数排成序列： 1： 0.a11 a12 a13 2： 0.a21 a22 a23 3： 0.a31 a32 a33 考虑数r =0.r1 r2 rk，其中当akk1则rk=1 ;当akk=1则 rk=2，k = 1,2, 。这样就保证了r不等于序列中任何数，因为对任意k，r的第k位rk与序列中第k号数的第k位akk不相等。 因为r不在序列中，所以，(0,1)是不可数集。,2020/9/4,离散数学,28,对角线方法,定理

15、4.3.3中所使用的方法称为对角线方法。,a11,a22,a33,r1,r1,r1,1 2 3 ,对角线方法是一种非常有用的方法。,2020/9/4,离散数学,29,连续统问题,已知N是可数集，而|N|R|.能否找到一个实数集R的子集A，使得： NAR ,但又不存在A到R的双射？,这个问题称为“连续统问题”。,现已证明：在现有公理系统中，证明它成立与否都不可能。,2020/9/4,离散数学,30,新春晓信息时代到，处处有电脑。夜来打字声，程序知多少？,答曰：,诗中的问题是计算机上所有程序有多少？,为何如此？,有诗为证：,计算机，靠程序，它的本事知底细。 程序都是符号串，理应是个可数集。,程序时

16、时新， 落花处处飘。 它们同为0 ，数数便知道。,2020/9/4,离散数学,31,第一篇的总结,集合； 关系； 映射； 可数集与不可数集。,本篇内容有：,2020/9/4,离散数学,32,集合,基本概念：,集合、子集、幂集。,集合之间的关系：,(真)含于( / )，相等()。,集合的基本运算：,并()、交()、差()和对称差()。,笛卡尔直积：,n个集合的笛卡尔直积是它们的 n元有序组的集合。它仍然是个集合。,集合的表示：,列举法和描述法。,2020/9/4,离散数学,33,关系,关系的概念：,A到B的二元关系R是笛卡尔直积AB的子集。,关系仍然是集合。,关系的表示：,仍然可以采用集合的表示

17、方法。,若A、B是有限集合，或者说R是有限集上的关系，则R的表示还可以采用：,关系矩阵 和 关系图。,2020/9/4,离散数学,34,关系的性质,自反性： x A xRx。 反自反性： x A (xRx)。 对称性： x ，yA， 若xRy yRx。 反对称性：x ，yA， 若xRy且yRx x = y 。 传递性： x ，y，zA， 若xRy且yRz xRz 。,令R是定义在集合A上的关系。,2020/9/4,离散数学,35,关系的运算,关系是集合，可具有集合的各种运算。 复合运算：RS = | 存在y B：xRy 且ySz，其中，R，S分别为A到B和B到C的关系。 逆关系：R-1 = |

18、 R。 注意复合运算的逆： (RS) 1 = S-1R-1。 在一个集合A上的关系的幂运算： R0 = | x A , Rk = Rk-1R 。,2020/9/4,离散数学,36,关系的闭包,某关系的具有某种性质的闭包是：包含该关系的最小的有此性质的关系。 依据关系的性质有：r(R)、 s(R)和t(R)，即自反闭包、对称闭包和传递闭包。 r(R) = RR0。 s(R) = RR-1。, t(R) =Ri。 i=1,2020/9/4,离散数学,37,用关系矩阵实现关系的运算,MRS = MR MS。 MR0为R0的关系矩阵。 显然R1的关系矩阵就是MRT。 显然的Rk关系矩阵是MRk = M

19、Rk-1 MR。 R的自反闭包为MRMR0。 R的对称闭包为MRMRT。 n R的传递闭包为 MRk。 k=1,令R、S为有限集上的关系，关系矩阵为MR 和 MS：,2020/9/4,离散数学,38,等价、划分和商集,集合A上的等价关系是具有自反性、对称性和传递性的关系。 集合A的划分是将A中所有元素分成若干非空的两两互不相交的集合。 集合A上的等价关系R可将A中的元素划分成等价类。这些等价类的集合称为A关于R的商集，记为A/R。 集合A上的关系R是等价关系当且仅当A/R是一个划分。所以A上的等价关系和A的划分是一一对应的。,2020/9/4,离散数学,39,序关系,集合A上的序关系是具有自反性、反对称性和传递性的关系。称 为偏序集。 任何两个元素均有序关系的偏序集为全序集。 极大(极小)元，最大(最小)元，上/下(确)界。 有限集上的序关系可用Hasse图表示。 任何非空子集均有最小元的偏序集为良序集。良序集一定是全序集，但反之不然。,2020/9/4,离散数学,40,映射,映射是每个象源都对应唯一映象的二元关系。 满射、单射和双射。 等