chap可数集与不可数集实用PPT课件

1、2021-10-221证明“”是一个等价关系证明：设S=X|任意两个元素之间存在双射，X是集合，是S上的二元关系： =|A,BS,存在双射:AB 1) 对每个AS,存在恒等映射I:AA，I是双射,于是AA，故是自反的。2) 对任意A,BS，若AB，则存在双射:AB，显然双射-1:BA存在，于是BA，故是对称的。3) 对任意A,B,CS，若AB,BC,则存在双射 :AB和:BC，而(A)=(A)=(B)=C，即双射:AC存在，于是AC，故是传递的。 综上所述，是等价关系。第1页/共39页2021-10-222有限与无限 定义4.1.2：设Nn=0,1, , n 1 , n1 ,若集合A与Nn等势

2、，则称A为有限集；否则称A为无限集。第2页/共39页2021-10-223无限多的自然数 定理4.1.1 自然数集合N是无限集。证明：设nN，n 1 , 令是从Nn到N的映射，Nn=0,1, , n1 ，下证不是双射。 令k=1+max(0), (1), , (n1) , 于是kN，但对任意xNn ,均有(x) k , 因此，不是满射，更不是双射。由定义4.1.2知，N为无限集。啊哈！这下我们知道有无限多个自然数了！第3页/共39页2021-10-224抽屉原理（鸽巢原理） 我们知道，若A，B均为有限集，且A与B之间存在双射，则A和B的元素个数相等，即AB。但是：定理4.1.2 任何有限集均不

3、能和其真子集等势。 此定理也称为抽屉原则：若将n+1个物体放入n个抽屉中，则至少有一个抽屉中放了两个或两个以上的物体。 抽屉原则对无限集并不总是成立，即无限集能够与其真子集等势。这是无限集合的一个非常重要的性质。 我们已经看到自然数集等势于它的真子集偶数集合。下面我们再看几个例子。第4页/共39页2021-10-225正实数和全体实数一样多例2： 令R和R+分别为实数集合和正实数集合，即R+=xR | x 0 ，显然，R+ R ，即R+是R的真子集。但是RR+ 证明：定义映射 f 如下： f (x) = ex , xR 于是，对任意的xR，存在唯一的yR+ ,使 y = ex = f (x)

4、； 另一方面，对任意的yR+ ,存在唯一的 x =lnyR , 使 f (x) = ex = elny = y , 这说明 f 是R到R+的一个双射。因此， RR+ 。 第5页/共39页2021-10-226例3：A=0, 1）, B=0, 1 , A,B R.显然 A B.构造一A到B的双射,说明AB.解: 令 A1=0,1/2,1/3,1/n,.作f: AB为: 任取x1,x2A, x1x2 , 显然, f(x1)f(x2) , 且对 任意yB:若y=0 , 则取x=0 , 有f(0)=0若y=1, 则取x=1/2A1, 于是f(1/2)=1/(2-1)=y若y=1/n,取x=1/(n+1

5、)A1,故f(1/(n+1)=1/n=y若yBA1,则取x=y,于是f(x)=x=y 综上所述f是A到B的双射,于是AB. f(0)=0 f(1/n)=1/(n-1) (n1 , 1/nA1 , nN) f(x)=x (x0,1)A1 )第6页/共39页2021-10-2274.2 集合的基数几个记号： 同有限集合中元素的个数的记法一样，集合A的基数用 |A|表示。 每个有限集合都恰与某个集合Nn= 0,1, , n1等势，其中n 0 , N0 = 。如果A Nn , 则A中有n个元素，即|A| = n; 若A为无限集，则用一个特殊的符号i(读作阿列夫i，i是一个正整数)来表示它的基数。例如，

6、对于自然数集合N，令|N| = 0 ( 读作 “ 阿列夫零 ” ) 。第7页/共39页2021-10-228如何比较集合的大小(1)若AB , 则称A的基数与B的基数相等, 记为|A|=|B|，否则记为|A|B|。(2)若存在A到B的单射，则称A的基数小于或等于B的基数，记为|A| |B|；或称B的基数大于或等于A的基数，记为|B| |A|。(3)若|A|B|，且|A|B| ，则称A的基数小于B的基数，记为|A| |A| 。 根据集合的基数来比较它们的大小。定义定义4.2.1 令A、B为两个集合， 由定义，|A|=|B|可形象地理解为A中的元素与B中的元素一样多。第8页/共39页2021-10

7、-229集合大小是可比的 定理4.2.1 设A和B为两个集合，总有 |A| |B|或者|B| |A| 。即任意两个集合总可比较大小。 像实数一样，任何两个基数都可以比较大小，所以有第9页/共39页2021-10-2210基数之间的相等关系是等价关系 定理4.2.2 基数之间的相等关系“= ”是一个等价关系,即对任何集合A , B和C, 有: (1)|A|=|A|; (2)若|A|=|B| ,则 |B|=|A|; (3)若|A|=|B|且|B|=|C| , 则|A|=|C| .第10页/共39页2021-10-2211基数间的是偏序关系 定理4.2.3 基数之间的小于或等于关系“ ”是一个偏序关

8、系,即对任何集合A , B和C, 有: (1)|A| |A|; (2)若|A| |B|且|B| |A| ,则 |A|=|B|; (3)若|A| |B|且|B| |C| , 则|A| |C| .第11页/共39页2021-10-2212几个关于基数的问题 我们知道自然数有无限多个。那么自然数集合是不是就是最大集合的呢？ 如果自然数集合不是最大的，那么比它更大的集合是什么样的呢？ 是不是存在最大的基数呢？ 不！不存在最大的集合。山外有山，天外有天。我们的口号是：只有更大，没有最大！第12页/共39页2021-10-2213山外青山楼外楼 定理4.2.4 对任意集合A,均有|A|(A) |,其中(A

9、)为A的幂集。 证明： 令 f : A(A)。f (a) =a， aA。 显然，f 是单射,于是|A| |(A)| . 显然，象集 a | aA 是(A)的真子集，所以，f 不是满射，从而不是双射。于是我们有|A| |(A)|。 错！错！错！错！错！错！错误是：虽然f不是双射，但不能说明A与 (A)之间不存在其它的映射是双射。正确的作法是证明A与 (A)存在任何的双射都是不可能的。 第13页/共39页2021-10-2214山外青山楼外楼 假设|A| = |(A)|，则存在A到(A)的双射g . 令B=aA | a g(a) (g(a)是a所对应的A的子集)，显然B(A)。bA,使g(b) =

10、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)| 。 讨论B的存在性：双射g：A(A)， aA，g(a)(A)即： g(a)是A的子集。又：作集合D=AA，AA，显然，D A，即D(A) 。令： aA，g(a)=D，于是，aD，即a g(a)，但aA A。第14页/共39页2021-10-

11、2215无限集也分大小，且无最大者 定理4.2.4说明：对任意无限集，它的幂集就比它大。因此对任意无限集都存在更大的集合。 我们记自然数集合N的幂集的基数为1，也就是| (N)| =1 ， 由定理4.2.4知， 0 1 。 可以证明 |R| = | (N)| , 其中R为实数集，于是， | N | |R|。实际上N是最小的无限集。 依次可以推得实数集合的幂集的基数为2，第15页/共39页2021-10-22164.3 可数集与不可数集定义4.3.1：设A是一个集合，若A与N等势，则称A为可数无限集；若A是有限集，则称A为可数集。 有时也将可数无限集简称为可数集。（遇到讨论可数集的问题时要注意区

12、分无限和有限两种情况。） 不是可数集的集合就称为不可数集。第16页/共39页2021-10-2217整数集是可数集例1：整数集Z是可数集。 证明：可定义N到Z的映射如下： (n) =n/2 (n为偶数） (n) =(1-n)/2 (n为奇数） 不难验证为双射,故NZ, 则Z是可数集。说明：映射 将 10，偶数正整数， 奇数（除1外） 负整数。第17页/共39页2021-10-2218定理4.3.1 A是可数无限集当且仅当A的所有元素可以如下编号排出： a1 , a2 , a3 , , an , 此定理告诉我们，任何集合只要它的元素可以排序，就是可数的。如何判别一集合是可数的第18页/共39页2

13、021-10-2219可数集的子集仍是可数的定理4.3.2 可数集的子集仍是可数集。 证明：设A是可数集，若A是有限集，则它的子集仍是有限集，当然也是可数集。若A是无限集，则由定理4.3.1知，A的元素可排列成： a1 , a2 , a3 , , an , (3.3) 显然，A的无限子集可如下得到： 从左向右看式(3.3)，可以依据子集中元素出现的次序将该子集的元素排列为： ai1 , ai2 , ai3 , , ain , 由定理4.3.1知，该子集是可数集。第19页/共39页2021-10-2220有理数集Q是可数集。 例2：有理数集是可数集。 证明：已知任何非零有理数均可表示成确定的既约

14、分数，故把全体有理数按如下方式排列： (1)0排在最前面； (2)对正分数，按它的分子与分母的和数由小到大排列，若和数相等，则分子小的排前面； (3)对负分数，把它紧排在相应的正分数后面。 显然，任意有理数总会排入此序列中。由定理4.3.1知，Q是可数集。 这种排序的方法称为字典排序法。第20页/共39页2021-10-2221三角形方法 有理数还可以按下表排序： 显然用此方法可将所有的有理数排序。分子分母 1 2 3 4 5 6 1234 . . . 此方法称为三角形方法，是很有用的方法。第21页/共39页2021-10-2222符号串的集合是可数的 令为一字母表， 上的符号串为+： + =

15、 1 +2 +3 +4+=i i=1 这里i为长度为i的符号串的集合。 +为可数集。 事实上，若| = k， 则每一个符号串就是一个 k 进制的数，显然它们是可以按序排列起来。所以+为可数集。 第22页/共39页2021-10-2223不是所有的集合都能排序 如果一个集合的元素可以排序，那么我们就可以一个一个地去数。 是不是所有的集合的元素都能排序呢？ 不！不是所有的集合都能排序。 比如0，1中实数的集合。让我们来设想一下将它的元素排一个序： 0理所当然排在第一位。 但是0之后应该排哪个呢？0.1？不！0.01？不！0.001？不！.？ 你会发现第二个就不知道排哪个好了。 这样看来实数集合是没

16、法去数了！?第23页/共39页2021-10-2224实数集是不可数的定理4.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不在序列中，所

17、以，(0,1)是不可数集。第24页/共39页2021-10-2225对角线方法 定理4.3.3中所使用的方法称为对角线方法。a11a22a33r1r2r31 2 3 对角线方法是一种非常有用的方法。第25页/共39页2021-10-2226连续统问题 已知N是可数集，而|N|R|.能否找到一个实数集R的子集A，使得： NAR ,但又不存在A到R的双射？ 这个问题称为“连续统问题”。 现已证明：在现有公理系统中，证明它成立与否都不可能。第26页/共39页2021-10-2227新春晓信息时代到，处处有电脑。夜来打字声，程序知多少？ 答曰： 诗中的问题是计算机上所有程序有多少？为何如此？有诗为证：

18、计算机，靠程序，它的本事知底细。程序都是符号串，理应是个可数集。程序时时新， 落花处处飘。它们同为0 ，数数便知道。第27页/共39页2021-10-2228集合论总结 集合； 关系； 映射； 可数集与不可数集。集合论的主要内容有：第28页/共39页2021-10-2229集合 基本概念：集合、子集、幂集。 集合之间的关系：(真)含于( / )，相等()。 集合的基本运算： 并()、交()、差()和对称差()。 笛卡尔直积： n个集合的笛卡尔直积是它们的 n元有序组的集合。它仍然是个集合。 集合的表示：列举法和描述法。第29页/共39页2021-10-2230关系 关系的概念： A到B的二元关

19、系R是笛卡尔直积AB的子集。 关系仍然是集合。 关系的表示：仍然可以采用集合的表示方法。 若A、B是有限集合，或者说R是有限集上的关系，则R的表示还可以采用：关系矩阵 和 关系图。第30页/共39页2021-10-2231关系的性质 自反性： x A xRx。 反自反性： x A (xRx)。 对称性： x ，yA， 若xRy yRx。 反对称性：x ，yA， 若xRy且yRx x = y 。 传递性： x ，y，zA， 若xRy且yRz xRz 。令R是定义在集合A上的关系。第31页/共39页2021-10-2232关系的运算 关系是集合，可具有集合的各种运算。 复合运算：RS = x，z

20、| yB：xRy 且ySz，其中，R，S分别为A到B和B到C的关系。 逆关系：R-1 = y，x | x，y R。 注意复合运算的逆： (RS) 1 = S-1R-1。 在一个集合A上的关系的幂运算： R0 =x，x | x A , Rk = Rk-1R 。第32页/共39页2021-10-2233关系的闭包 某关系的具有某种性质的闭包是：包含该关系的最小的有此性质的关系。 依据关系的性质有：r(R)、 s(R)和t(R)，即自反闭包、对称闭包和传递闭包。 r(R) = RR0。 s(R) = RR-1。 t(R) =Ri。 i=1第33页/共39页2021-10-2234用关系矩阵实现关系的运算 MRS = MR MS。 MR0为R0的关系矩阵。 显然R-1的关系矩阵就是MRT。 显然的Rk关系矩阵是MRk = MRk-1 MR。 R的自反闭包为MRMR0。 R的对称闭包为MRMRT。 n R的传递闭包为 MRk。 k=1令R、S为有限