1.1-集合的基本概念

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,离 散 数 学,(,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,、吉林大学计算机学院,2009,级的本科学生可以看成是一个集合；,4,、这间教室中的所有座位可以看成是一个集合。,例如,:,集合的元素,(,member,或,element,),组成一个集合的那些对象或单元称为这个集合的元素。,通常，用小,写的英文字母,a,b,c,表示,集合中的元素,设,A,是一个集合，,a,是集合,A,中的元素，记以,a,A,，,读作,a,属于,A,；若,a,不是集合,A,中的元素，则记以,a,A,，,读作,a,不属于,A,。,例如：,A,是正偶数集合，则,2,A,，,8,A,，,36,A,；,而,3,A,，,9,A,，,17,A,属于,(,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=a,2,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,1A=1,a,*,-3,a,b,x|x,是汽车,地球,多样性,设集合,S=A|A,是集合，且,A,A,若,S,S,，则,S,是,集合,S,的,元素，但根据,S,的,定义，有,S,S,，,与假设矛盾；,若,S,S,，则,S,是不以自身为元素的集合，但根据,S,的定义，有,S,S,，,与假设矛盾；,罗素悖论,(,Russells paradox,),当,两个集合,A,和,B,的元素完全一样，即,A,，,B,实际上是同一个集合时，则称集合,A,，,B,相等，记以,A=B,。,例：设,A=x|x,是偶数，且,0 x10,，,B=2,4,6,8,，则,A=B,。,【,定义,1,】,集合相等,设,A,，,B,是两个集合，若,A,的元素都是,B,的元素，则称,A,是,B,的子集，也称,B,包含,A,，或,A,包含,于,B,，,记以,A,B,，或,B,A,。,若,A,B,，且,A,B,，则称,A,是,B,的真子集,(,proper subset,),，,也称,B,真包含,A,，或,A,真包含,于,B,，,记以,A,B,，或,B,A,。,【,定义,2,】,子集,(,subset,),设,A=2,4,6,8,，,B=x|x,是正偶数,，,C,=,x|x,是整数,则有,A,B,，,B,C,，,A,C,并且,A,B,，,B,C,，,A,C,。,例：,对任意集合,A,有,A,A,。,空集是任意集合的子集，且空集是唯一的。,对于任意两个集合,A,、,B,，,A=B,当且仅当,A,B,且,B,A,。,重要结论,是否存在集合,A,和,B,使得,A,B,且,A,B,？,若存在，请举一例。,设,A=a,，,B=a,a,b,c,，,则有,:,A,B,且,A,B,再,例如：,且,讨论,：,设,A,是集合，,A,的所有子集为元素做成的集合称为,A,的幂集，记以,(,A,),或,2,A,。,(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,，,则,|2,A,|=C,n,0,+C,n,1,+,+,C,n,n,=2,n,。,x,(A),当且仅当,x,A,。,设,A,、,B,是两个集合，,A,B,当且仅当,(A),(B),；,幂集的性质,设,C,是一个集合。若,C,的元素都是集合，则称,C,为集合族。,若集合族,C,可表示为,C=,S,d,d,D,，,则称,D,为集合,族,C,的标志（索引）集。,【,定义,4,】,集合族、标志集,显然，,2,A,是一个集合族。,设,A,1,A,2,A,3,是集合的序列，且两两之间互不相同，则集合,A,1,A,2,A,3,是一个集合族，可表示为,A,i,|i,N,，,其中,N,是自然数集合，是该集合的标志集合。,设,A,，,B,是两个集合。所有属于,A,或者属于,B,的元素做成的集合，称为,A,和,B,的并集，,记以,A,B,。即,A,B=x|x,A,或,xB,例如，令,A=a,，,b,，,c,，,d,，,B=c,，,d,，,e,，,f,，,于是,A,B=a,，,b,，,c,，,d,，,e,，,f,。,【,定义,5】,集合的并集,(,Union,),并集的文氏图,A,B,A,B,设,A,，,B,是两个集合。由属于,A,又属于,B,的元素组成的集合，称为,A,和,B,的交集,，,记以,A,B,。,即,A,B=x|x,A,且,xB,例如，令,A=a,，,b,，,c,，,d,，,B=c,，,d,，,e,，,f,，,于是,A,B=c,，,d,。,【,定义,6】,集合的交集,(,Intersection,),交集的文氏,图,A,B,A,B,设,A,1,，,A,2,，,，,A,n,是,n,个集合，则，,A,1,A,2,A,n,，,简记为,A,1,A,2,A,n,，,简记为,并集和交集的推广,设,A,1,，,A,2,，,，,A,n,是,n,个集合，则,容斥原理,(principle of inclusion-excl