集合的基本概念1.ppt

离 散 数 学 (I),主讲教师：李占山 计算机楼A338 E-mail:,课程安排,本学期讲课学时：64 课程性质：必修 离散数学孙吉贵等 -高等教育出版社 参考教材: 1离散数学-学习指导与习题解答孙吉贵等 -高等教育出版社 2集合论与图论耿素云编著北京大学出版社 3离散数学-精讲精解精练黄健斌编著西安电子科技大学出版社,离散数学(I),第一章 集合论基础 第二章 命题逻辑 第三章 一阶逻辑 第四章 图与网络 第五章 数论基础,第一章 集合论基础,1.1 集合的基本概念 1.2 关 系 1.3 映 射,集合论与第三次数学危机,集合是一个原始概念,最初是从分析数学中产生的。1854年德国数学家黎曼在研究傅氏级数时，得出结论说：“若f(x)在区间上除有限个第一类间断点外是连续的，则在连续点，函数的三角函数收敛到函数值。”这时需要考虑这些连续点的整体，于是人们逐渐产生了点的集合的原始概念；对于集合概念的提出，起首要作用的人物是德国大数学家康托尔，他是数学史上公认的集合论的创始人。1871年，他给出集合的第一个定义，且引入点集的极限点、闭集、开集、交集、并集等概念，1874年康托尔证明了代数数与有理数集的可数性和实数集的不可数性，1878年他又引入集合“势”的概念。 康托尔的工作具有革命性，一时难以被多数数学家接受，但数学的历史已有结论表明康托尔的集合论是分析数学与离散数学不可或缺的有力工具。为此我们来了解一下康托尔与罗素,康托尔 (Cantor),康托尔简介,康托尔(Georg Cantor)1845年出生于俄罗斯的圣彼德堡，康托尔十多岁时就对数学产生了浓厚的兴趣。1862年他在苏黎世开始了他的大学学习，1863年又在柏林大学继续学习，并得到著名数学家外尔斯特拉斯、库默尔和克罗内克的指导。特别是受了外尔斯特拉斯的影响而专攻纯粹数学，1866年完成了一篇数论方面的博士论文后获得博士学位。1869年康托尔得到了哈雷大学的一个职位，1879年任哈雷大学教授。1891年，康托尔组建德国数学家联合会，任第一任主席。1904年，伦敦皇家学会授予他最高荣誉：西尔威斯特（slvester)奖章。,康托尔这个人是数学界的奇才，他为数学的新奇思路和独特创造以及丰富的想象力，成为当时数学界有争议的人物。但最终成为后世数学家学习与敬仰的模范。康托尔的老师克罗内克是个“有穷论者”，他反对康托尔的“超穷数”的集合论观点，他不仅对康托尔的学术工作粗暴攻击，还竭力阻止康托尔去柏林大学工作，由于克罗内克的权威地位，使得其他数学家也跟着攻击康托尔的工作，使康托尔试图在柏林大学得到一个更高待遇的计划受挫。1918年死于精神病诊所。,康托尔最著名的著作是1895-1897年出版的超穷理论基础（两卷集），康托尔指出，数学理论必须肯定实无穷，因为很多最基本的数学性质，例如一切正整数，圆周上的一切点等，事实上都是实无穷性的概念。而且不能把能有穷所具有的性质强加于无穷。他的“一一对应”的原理突破了传统的“整体大于部分”的旧观念，例如全体正整数与（其部分）全体正偶数一一对应，正整数集与正偶数集等势，相当于传统上的“个数相等”。 康托尔的集合论现在称为朴素集合论，1871年他对集合给了一个朴素的限制宽松的定义；“把一定的并且彼此可以明确识别的事物（这种事物可以是直观的对象，也可以是思维的对象）放在一起，称为一个集合，这些事物中的每一个称为该集合的一个元素。,罗素简介,罗素（Bertrand Russell,1872-1970)生于一个以积极参与进步运动，热烈地投身于自由事业而著名的英格兰家庭。年幼就成为孤儿的罗素由祖父抚养，并在家里接受教育。1890年他进入剑桥的Trinity学院学习数学和论理学，并由于在几何学方面的工作突出为他赢得了一个研究员位置。1910年Trinity学院任命他教授逻辑和数学原理的课程。罗素最伟大的工作是他提出的可以作为所有数学学科基础的原理。他最著名的文章是与人合作的Principia Mathematica，这篇文章试图用一组基本公理推导出所有的数学。此外，他还写了包括哲学、物理和他的政治观点的很多书籍，1950年罗素赢得诺贝尔文学奖。,大厦基兮矗云天， 数学砥柱兮两撑竿。 集合论兮康托儿峰颠巅， 逻辑理兮舌战群儒无辩。,1.1 集合的基本概念,什么是集合(Set)？ “所要讨论的一类对象的整体”； “具有同一性质单元的集体” 通常，用大写的英文字母A, B, C,表示集合；,1、二十六个英文字母可以看成是一个集合； 2、所有的自然数看成是一个集合； 3、吉林大学计算机学院2007级的本科学生可以看成是一个集合； 4、这间教室中的所有座位可以看成是一个集合。,例如:,集合的元素(member或element),组成一个集合的那些对象或单元称为这个集合的元素。 通常，用小写的英文字母a, b, c,表示集合中的元素,设A是一个集合，a是集合A中的元素，记以aA，读作a属于A；若a不是集合A中的元素，则记以aA，读作a不属于A。 例如：A是正偶数集合，则2A，8A，36A；而 3A，9A，17A,属于(belong to),包含有限个元素的集合，称为有限集或有穷集(finite set)； 包含无限个元素的集合，称为无限集或无穷集(infinite set )。 例：所有英文字母组成的集合是有限集，整数集合是无限集。,有限集 、无限集,约定，存在一个没有任何元素的集合，称为空集(empty set) ，记为，有时也用来表示。 约定，所讨论的对象的全体称为全集(universal set)，记作E或U，我们所讨论的集合都是全集的子集 。全集是相对的。,空集、全集,设A是有穷集合， A中元素的个数称为集合A的元素数，记为A。 例如，设A是所有英文字母组成的集合，则A=26。 特别， | |=0,集合的元素数,列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1,4,9,16,25,36。 描述法 ；通过描述集合中元素的共同特征来表示集合，例如： V= x|x是元音字母 ，B= x|x=a2 , a是自然数,集合的表示法,文氏图(Venn Diagram) 用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。 例如：集合V=a,e,i,o,u ，用文氏图表示如下:,E,V,a,u,确定性； 互异性； 无序性； 多样性；,集合的特征,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一； 例如：A=x|x是自然数，且x100 B=x|x是年轻人 C=x|x是秃子,确定性,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。 例如： 集合A=a,b,c,c,b,d，实际上，应该是A=a,b,c,d,互异性,集合与其中的元素的顺序无关 例如： 集合a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a，都是表示同一个集合。,无序性,集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。 例如： A=a,a,a,b,a, 1 A=1,a,*,-3,a,b,x|x是汽车,地球,多样性,设集合S=A|A是集合，且AA 若SS，则S是集合S的元素，但根据S的定义，有S S，与假设矛盾； 若SS，则S是不以自身为元素的集合，但根据S的定义，有SS，与假设矛盾；,罗素悖论(Russells paradox),当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记以A=B。 例：设A=x|x是偶数，且0x10，B=2,4,6,8，则A=B。,【定义1】集合相等,设A，B是两个集合，若A的元素都是B的元素，则称A是B的子集，也称B包含A，或A包含于B，记以A B，或B A 。 若AB，且AB，则称A是B的真子集(proper subset)，也称B真包含A，或A真包含于B，记以AB，或B A 。,【定义2】子集(subset),设A=2,4,6,8 ，B= x|x是正偶数， C=x|x是整数,则有A B，B C，AC,并且A B，B C，A C 。,例：,对任意集合A, 有A A。 空集是任意集合的子集，且空集是唯一的。 对于任意两个集合A、B，A=B当且仅当AB且BA。,重要结论,是否存在集合A和B, 使得AB 且A B ？若存在，请举一例。 设A=a ，B=a,a,b,c，则有: AB 且A B 再例如： 且 ,讨论：,设A 是集合，A的所有子集为元素做成的集合称为A的幂集，记以(A)或 2A。 (A)=S|S A 例： A=a,b,c ，则 (A)=,a,b,c,a,b,a,c,b,c,a,b,c,【定义3】幂集(power set),若A为有穷集，|A|=n，则 |2A | = Cn0 + Cn1 + + Cnn =2n 。 x(A)当且仅当xA。 设A、B是两个集合，AB当且仅当(A)(B)；,幂集的性质,设C是一个集合。若C的元素都是集合，则称C为集合族。 若集合族C可表示为C=SddD，则称D为集合族C的标志（索引）集。,【定义4】集合族、标志集,显然，2A是一个集合族。 设A1, A2, A3, 是集合的序列，且两两之间互不相同，则集合A1, A2, A3, 是一个集合族，可表示为Ai| iN，其中,N是自然数集合，是该集合的标志集合。,设A，B是两个集合。所有属于A或者属于B的元素做成的集合，称为A和B的并集，记以AB。即AB=x|xA或xB 例如，令A=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。,【定义5】集合的并集(Union),并集的文氏图,A,B,AB,设A，B是两个集合。由属于A又属于B的元素组成的集合，称为A和B的交集，记以AB。即AB=x|xA且xB 例如，令A=a，b，c，d，B=c，d，e，f，于是AB=c，d。,【定义6】集合的交集(Intersection),交集的文氏图,A,B,AB,设A1，A2，An是n个集合，则， A1A2An ，简记为 A1A2An ，简记为,并集和交集的推广,设A1，A2，An是n个集合，则,容斥原理 (principle of inclusion-exclusion),称为包含排斥原理，简称容斥原理。,设A，B是两个集合。由属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，记以A-B，或AB。 即A-B=x|xA且xB 例如，令A=a，b，c，d，B=c，d，e，f，于是A - B=a，b。,【定义7】集合的差集(Difference),差集的文氏图,A,B,A-B,E,设A是一个集合，全集E与A的差集称为A的余集或补集，记以A。即A=E-A 例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。 特别，,【定义8】集合的补集(Complement),补集的文氏图,A,A的补集,E,设A，B是两个集合。则A与B的环和(对称差),记以AB, 定义为AB=(A-B)(B-A)。 A与B的对称差还有一个等价的定义，即AB=(AB)-(AB)。 例：令A=a，b，c，d，B=c，d，e，f，于是AB=a，b， e，f。,【定义9】集合的对称差,对称差的文氏图,A,B,AB,E,设A，B是两个集合，则A与B的环积定义为 A B = AB,【定义10】集合的环积,A,B,E,我们将(a1,a2 , ,an)称为有序n元组，其中，a1是其第一个元素， a2是其第二个元素， ，an是其第n个元素。 两个有序n元组(a1,a2 , ,an)和(b1,b2 , ,bn)相等当且仅当ai=bi , i=1,2,n,【定义11】有序n元组(ordered n-tuple),对于有序n元组，当n=2时，我们将其称作有序二元组，也称作有序对,或序偶。 有序对的特点： 若ab,则(a,b)(b,a) 两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d,【定义12】有序对(ordered pairs),阅读与欣赏 笛卡儿的梦 笛卡儿（15961650年）法国著名的数学家，青年时期曾参加军队到荷兰。1619年的冬天，莱茵河畔乌儿小镇的军用帐篷中。入夜， 万簌俱静，笛卡儿彻夜不眠，沉迷在深思之中，他望着天空，想着怎么用几个数字来表示星星的位置呢？自己随军奔波，给家里去信怎么报告自己的位置呢？他完全进入数学的世界，继续进行着数与形的冥想 他仿佛到了无人的旷野，他的排长站在他的面前说：“你不是想用数学来解释自然界吗？”排长说着抽出了两支箭，拿在手里搭成一个十字架，箭头一个向上，一个朝右。他将十字架举过头说：“你看，假如我们把天空的一部分看成是一个平面，这个天空就被分成四个部分。这两支箭能射向无限远，天上随便那颗星星，你只要向这两支箭上分别引垂线段，就会得到两个数字，这星的位置就一清二楚了。”笛卡儿还不清楚又问道“负数又该怎样表示呢？”排长笑道：“两支箭的十字交叉处定为零，向上向右为正数，向下向左不就是负数了吗？”笛卡儿高兴地扑了过去，却扑通一声跌入河中正在大喊，却被人叫醒 ，天已大亮了。笛卡儿发疯似地拿出本子和铅笔，把梦中见到的全都画了出来。后人传说笛卡儿创立的直角坐标系就是这样从梦中得来的。 直角坐标系的创立，为用代数方法研究几何问题开辟了一条崭新的道路，引起了数学的深刻革命。为了纪念笛卡儿，直角坐标系也叫笛卡儿坐标系。,设A，B是两个集合，所有有序对(x, y)做成的集合(其中xA，yB)，称为A，B的直乘积(笛卡儿积)，记以AB。 AB=(x，y)xA且yB。,【定义13】笛卡儿积(Cartesian product),设A1,A2 , ,An是n个集合，由所有有序n元组(a1,a2,an)做成的集合(其中aiAi，i=1,2, ,n)，称为A1,A2,An的直