集合论

电子科技大学离散数学课程组——国家精品课程离散数学数学科学学院2020年1月30日星期四任课教师:杨春电子科技大学离散数学课程组——国家精品课程67-22020/1/301.3无限集质变无限集合无法用确切的元素个数来描述，因此，无限集合有许多有限集合所没有的一些特征，而有限集合的一些特征也不能任意推广到无限集合中去，即使有的能推广，也要做某些意义上的修改。有限集无限集量变电子科技大学离散数学课程组——国家精品课程67-32020/1/301.3.1可数集合和不可数集合二十世纪初，集合成为数学的基本概念之后，由冯•诺依曼（VonNeumann，J）用集合的方式来定义自然数取得了成功，提出了用序列Φ，{Φ}，{Φ,{Φ}}，{Φ,{Φ},{Φ,{Φ}}}，······来定义自然数。电子科技大学离散数学课程组——国家精品课程67-42020/1/30自然数集合N的定义N，若nN，则n′:＝n{n}N。也即：0:＝，1:＝{}＝{0}，2:＝{,{}}＝{0,1}...n:＝{0,1,2,3,...n-1}...故N＝{0,1,2,3,...,n,...}电子科技大学离散数学课程组——国家精品课程67-52020/1/30等势的概念定义1.3.1设A，B是两个集合，若在A，B之间存在1-1对应的关系：ψ：A→B则称A与B是等势的(equipotential)，记为：AB。也称集合A与B等势(equipotent)。注意：若A＝B，则AB。若AB，则A＝B（×）（∨）电子科技大学离散数学课程组——国家精品课程67-62020/1/30可数集合(可列集）定义1.3.2凡是与自然数集合等势的集合，统称为可数集合(可列集)(CountableSet)。可数集合记为：א0(读作阿列夫零)。例1.3.1下列集合都是可数集合：1)O+＝{x|xN，x是正奇数};2)P＝{x|xN，x是素数};3)有理数集合Q.电子科技大学离散数学课程组——国家精品课程67-72020/1/30解：1）在O+与N之间建立1-1对应的关系f：N→O+如下：N０１２３４...ｎ...ｆ↓↓↓↓↓...↓...O+１３５７９...2n+1...所以，O+是可数集合。电子科技大学离散数学课程组——国家精品课程67-82020/1/302）在P与N之间建立1-1对应的关系f：N→P如下：N０１２３４...ｆ↓↓↓↓↓...P２３５７11...所以，P是可数集合。电子科技大学离散数学课程组——国家精品课程67-92020/1/303）…-3/1[18]-2/1[5]-1/1[4]0/1[0]1/1[1]2/1[10]-3/1[11]……-3/2[17]-2/2-1/2[3]0/21/2[2]2/23/2[12]……-3/3-2/3[6]-1/3[7]0/31/3[8]2/3[9]3/3…-3/4[16]-2/4-1/4[15]0/41/4[14]2/43/4[13]…所以，有理数集合必是可数集合。→电子科技大学离散数学课程组——国家精品课程67-102020/1/30定理1.3.1两个有限集合等势当且仅当它们有相同的元素个数；有限集合不和其任何真子集等势；可数集合可以和其可数的真子集等势。电子科技大学离散数学课程组——国家精品课程67-112020/1/30不可数集合定义1.3.3开区间(0,1)称为不可数集合，其基数设为א(读作阿列夫)；凡是与开区间(0,1)等势的集合都是不可数集合。电子科技大学离散数学课程组——国家精品课程67-122020/1/30例1.3.2(1)闭区间[0,1]是不可数集合；(2)实数集合R是不可数集合。解（1）在闭区间[0,1]和开区间(0,1)之间建立如下对应关系：nn+20→1/4,1→1/2,R:11→n=1,2,3,L,22n→n其他n(0,1).电子科技大学离散数学课程组——国家精品课程67-132020/1/30例1.3.2(续)则上述对应是一一对应的关系。所以[0，1]与（0，1）一定是等势的，即[0，1]是不可数集合。（2）在实数集Ｒ和开区间(0,1)之间建立如下对应关系：显然此对应关系是一一对应关系，即（0，1）与R之间是等势的，所以R是一个不可数集合。2n-1n→tanπ2电子科技大学离散数学课程组——国家精品课程67-142020/1/301.4集合的应用例1.4.1用H代表硬币正面，T代表硬币反面。试写出当扔出三个硬币时可能出现的结果所组成的集合。解:8种可能：{HHH，HHT，HTH，HTT，THH，THT，TTH，TTT}。但这三个硬币没有顺序之分，即HHT和HTH是同一个元素，所以A={HHH，HHT，HTT，TTT}。电子科技大学离散数学课程组——国家精品课程67-152020/1/30例1.4.2一个正三角形被均分为三个小三角形，如图1.4.1所示。现用黑、白二色对其小三角形着色，假设经旋转能使之重合的图像算一种。试写出由不同图像构成的集合。图1.4.1图1.4.2电子科技大学离散数学课程组——国家精品课程67-162020/1/30解因为每个小三角形均可着色，三个小三角形共有2×2×2=8种着色方案，所以可得8种不同的图像。又因为经旋转能使之重合的图像算一种，所以共有4种不同的着色方案。因此由不同图像构成的集合为{1,2,3,4}。1432电子科技大学离散数学课程组——国家精品课程67-172020/1/30容斥原理定义2.4.1所谓容斥，是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿。这种原理称为容斥原理(ThePrincipleofInclusion-exclusion)，又称为包含排斥原理。电子科技大学离散数学课程组——国家精品课程67-182020/1/30定理2.4.1设A和B是任意有限集合，有|A∪B|=|A|＋|B|－|A∩B|。分析由图容易看出，A∪B=(A-B)∪(A∩B)∪(B-A)，A=(A-B)∪(A∩B)B=(A∩B)∪(B-A)UABA-BB-A|A|=|A-B|+|A∩B||B|=|A∩B|+|B-A||A∪B|=|A-B|+|A∩B|+|B-A|推论2.4.2设U为全集，A和B是任意有限集合，则ABU(AB)AB电子科技大学离散数学课程组——国家精品课程67-192020/1/30例2.4.1对所给的集合：A={1,2,3,4}，B={2,3,5,6,8}；验证定理2.4.1。解:A∪B={1,2,3,4,5,6,8}A∩B={2,3},又|A|=4,|B|=5，|A|＋|B|－|A∩B|=4＋5－2=7=|A∪B|所以：电子科技大学离散数学课程组——国家精品课程67-202020/1/30三个集合的情形定理2.4.3设A，B和C是任意三个有限集合，有推论2.4.4设U为全集，A，B和C是任意有限集合，则A∪B∪C=(A+B+C)-(A∩B+A∩C+B∩C)+A∩B∩CA∩B∩C=U-(A+B+C)+(A∩B+A∩C+B∩C)-A∩B∩C电子科技大学离散数学课程组——国家精品课程67-212020/1/30例2.4.2调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人对三种课程都选修。问（1）调查中三种课程都不选的学生有多少？（2）调查中只选修计算机科学课程的学生有多少？电子科技大学离散数学课程组——国家精品课程67-222020/1/30例2.4.2解设A、B、C分别表示选修数学课程，计算机课程和商贸课程的人构成的集合.则三种课程都不选的学生集合为，只选修计算机科学课程学生的集合为UABCA∩B∩CA∩B∩C电子科技大学离散数学课程组——国家精品课程67-232020/1/30例2.4.2解（续）（1）∵|U|=260,|A|=64,|B|=94,|C|=58,|A∩C|=28,|A∩B|=26,|B∩C|=22,|A∩B∩C|=14，所以利用容斥原理得=106（2）A∩B∩C=U-(A+B+C)+(A∩B+A∩C+B∩C)-A∩B∩CA∩B∩C=B-A∩B-B∩C+A∩B∩C=94-26-22+14=60电子科技大学离散数学课程组——国家精品课程67-242020/1/30容斥原理的推广定理2.4.5设A1,A2,…,An是任意n个有限集合，则推论2.4.6设U为全集，A1,A2,…,An是任意n个有限集合，则n12niijijki=1i≠ji≠j≠kn+112nA∪A∪∪A=A-A∩A+A∩A∩A++(-1)A∩A∩L∩A。m12niijijki=1i≠ji≠j≠kn12nA∩A∩∩A=S-A+A∩A-A∩A∩A++(-1)A∩A∩∩A。电子科技大学离散数学课程组——国家精品课程67-252020/1/30例2.4.3对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别为13、5、10和9。其中同时会英语、日语的人数为2；同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的人数均为4；会日语的人既不会法语也不会德语。试求(1)只会一种语言的人数各为多少？(2)同时会英、德、法语的人数为多少？电子科技大学离散数学课程组——国家精品课程67-262020/1/30解设A、B、C、D分别为会英、日、德、法语的人的集合，由已知条件可知：|A|＝13，|B|＝5，|C|＝10，|D|＝9，|A∩B|＝2，|A∩C|＝|A∩D|＝|C∩D|＝4，|B∩C|＝|B∩D|＝0,|A∩B∩C|＝|A∩B∩D|＝|B∩C∩D|＝0，|A∩B∩C∩D|＝0，|A∪B∪C∪D|＝24，电子科技大学离散数学课程组——国家精品课程67-272020/1/30解（续）利用容斥原理，并代入已知条件得24＝13＋5＋10＋9－2－4－4－4－0－0＋0＋0＋0＋|A∩C∩D|－0。得：|A∩C∩D|＝1，即同时会英、德、法语的只有1人。电子科技大学离散数学课程组——国家精品课程67-282020/1/30例2.4.3解（续）设只会英、日、德、法语的人数分别为x1,x2,x3,x4，则x1＝|A|－|(B∪C∪D)∩A|＝|A|－|(B∩A)∪(C∩A)∪(D∩A)|对B∩A、C∩A、D∩A应用容斥原理，得|(B∩A)∪(C∩A)∪(D∩A)|＝2＋4＋4－0－0－1＋0＝9故，x1＝13-9＝4。类似地可求出：x2＝3，x3＝3，x4＝2。电子科技大学离散数学课程组——国家精品课程67-292020/1/30例1.4.4在20个大学生中，有10人爱好音乐，有8人爱好美术，有6人既爱好音乐又爱好美术。问既不爱好音乐又不爱好美术的学生有多少个？解设所有的大学生的集合为U，爱好音乐的学生集合为A，爱好美术的学生集合为B。则既不爱好音乐又不爱好美术的学生组成的集合为。如右图：ABA∩BUAB电子科技大学离散数学课程组——国家精品课程67-302020/1/30解根据已知有|U|=20，|A|=10，|B|=8，||=6又因为，||=|A|+|B|-||=10+8-6=12从而，||=|U|-||=20-12=8即不爱好音乐又不爱好美术的学生有8个。A∩BA∪BA∩BA∩BA∪B电子科技大学离散数学课程组——国家精品课程67-312020/1/301.5本章总结1.与集合相关的概念和特殊集合：集合的定义、集合的表示、属于和不属于、子集、真子集、包含和真包含、幂集、空集、全集、基数、有限集、无限集等；2.与集合运算相关的概念和定理：集合的交、并、差、补和对称差等五种运算的定义及相关定理。电子科技大学离散数学课程组——国家精品课程67-322020/1/30习题类型1.基本概念题：涉及集合的表示