离散数学第三章 集合论

,第三章集合论,离散数学陈志奎主编人民邮电出版社,集合论的创立与康托尔的遭遇,19世纪末期，数学界出现了一件引人注目的事情。一位名叫格奥尔格康托尔（G.Cantor，18451918）的德国数学家提出一种令人费解的古怪理论-集合论。它的内容是如此与常识格格不入，以致于一出世就引起了一场轩然大波。,集合论的创立与康托尔的遭遇,自从17世纪牛顿和莱布尼茨创立微积分理论体系之后，在近一二百年时间里，微积分理论一直缺乏一个严格的逻辑基础。出于这一目的，康托尔用集合的观点重新考察各种数量关系，特别是无穷数量关系。,在无穷的世界里，整体的所有元素和部分的所有元素之间可以是一一对应的。另外，无穷集合并不都是相等的，比如所有实数和所有有理数之间就不是一一对应的。因而，无穷集合是有大小的。集合论用“基数”这个概念来表示无穷集合间的区别。,集合论的创立与康托尔的遭遇,康托尔的研究成果发表之后，遭到了德国数学家克隆尼克的激烈攻击。,“上帝创造了自然数，其余的一切才是人做的工作”,集合论的创立与康托尔的遭遇,法国数学家彭加勒说：“我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西”。他把集合论当作一个有趣的“病理学的情形”来谈，并且预测说：“后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了”。德国数学家魏尔认为，康托尔关于基数的等级观点是雾上之雾。菲利克斯克莱因也不赞成集合论的思想。数学家HA施瓦兹原来是康托尔的好友，但他由于反对集合论而同康托尔断交,公理化集合论的建立,在1900年第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣布“数学已被算术化了。今天，我们可以说绝对的严格已经达到了。”然而这种自得的情绪并没能持续多久。不久，集合论有漏洞的消息迅速传遍了数学界。这就是1902年罗素得出的罗素悖论。,公理化集合论的建立,罗素构造了一个所有不属于自身（即不包含自身作为元素）的集合R。现在问R是否属于R？,如果R属于R，则R满足R的定义，因此R不应属于自身，即R不属于R；另一方面，如果R不属于R，则R不满足R的定义，因此R应属于自身，即R属于R。这样，不论何种情况都存在着矛盾。,公理化集合论的建立,1908年，策梅罗提出公理化集合论，后经改进形成无矛盾的集合论公理系统，简称ZF公理系统。这就是集合论发展的第二个阶段：公理化集合论。在1908年以前由康托尔创立的集合论被称为朴素集合论。,集合的概念及其表示,集合的运算及恒等式,有穷集的计数和包含排斥原理,主要内容,3.1集合的概念及其表示,集合是一个不能精确定义的基本概念。一般地说，把具有共同性质的一些事物汇集成一个整体，就叫做集合。而这些事物就是这个集合的元素。例如，全体中国人是一个集合，每个中国人都是这个集合的元素；全体自然数是一个集合，每个自然数都是这个集合的元素；图书馆的藏书是一个集合，每本书都是这个集合的元素；全国的高校也形成一个集合，每所高校都是这个集合的元素。集合一般用大写的英文字母表示，集合中的事物，即元素用小写的英文字母表示。若元素属于集合，记作，读作“属于”；反之，写作，读作“不属于”。一个集合的元素个数是有限的，则称作有限集，否则称作无限集。,10,3.1集合的概念及其表示,1枚举法：把集合中的元素写在一个花括号内，元素间用逗号隔开。例如：2构造法：构造法又叫谓词法。如果是表示元素x具有某种性质P的谓词，则所有具有性质P的元素构成了一个集合，记作。显然，。例如：,11,集合的表示法,3.1集合的概念及其表示,集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如集合的元素是无序的，如但集合中的元素还可以是集合。例如应该说明的是，但，同理但。,12,集合的表示法,3.1集合的概念及其表示,在本书中定义一些通用的集合的符号，自然数集合N，整数集合Z，有理数集合Q，实数集合R，复数集合C。为了体系上的严谨性，我们规定，对于任何集合A都有。,13,3.1集合的概念及其表示,14,集合间的关系,3.1集合的概念及其表示,15,集合间的关系,3.1集合的概念及其表示,定理3.1空集是任意集合的子集，即对于任意集合A，有,16,集合间的关系,3.1集合的概念及其表示,定义3.6给定集合A，由集合A的所有子集为元素组成的集合称为集合A的幂集，记为。例如定理3.2若有限集合A有n个元素，则它的幂集有个元素。,17,集合间的关系,集合的概念及其表示,集合的运算及恒等式,有穷集的计数和包含排斥原理,主要内容,3.2集合的运算及恒等式,集合之间的关系和初级运算可以用文氏图给予形象的描述。文氏图的构造方法是首先画一个大矩形表示全集（有时为简单起见可将全集省略），其次在矩形内画一些圆（或任何其他适当的闭曲线），用圆的内部表示集合。不同的圆代表不同的集合。如图3.1所示，图中的阴影部分表示新组成的集合。图3.1文氏图表示集合关系集合的运算，就是以给定集合为对象，按确定的规则得到另外一些集合。集合的基本运算有并、交，相对补，绝对补和对称差。,19,3.2集合的运算及恒等式,集合的运算，就是以给定集合为对象，按确定的规则得到另外一些集合。集合的基本运算有并、交，相对补，绝对补和对称差。,20,3.2集合的运算及恒等式,定义3.7设A，B为集合，A与B的并集，交集，B对A的相对补集分别定义如下。由定义可以看出，是由A或B中的元素构成，由A和B中的公共元素构成，由属于A但不属于B的元素构成，例如则有如果两个集合交集为，则称这两个集合是不交的，例如B和C是不交的。,21,3.2集合的运算及恒等式,定义3.8设A，B为集合，A与B的对称差集定义为例如则定理3.3证明等式,22,3.2集合的运算及恒等式,定义3.9设E为全集，A为一集合，则的绝对补集定义为因为E是全集，是永真命题，所以可以定义为例如，则,23,3.2集合的运算及恒等式,以上所定义的集合之间的基本运算的文氏图表示可以参考图3.2。,24,3.2集合的运算及恒等式,根据以上对集合基本运算的定义，可以得到集合论中的关于集合运算的基本定律。,25,集合运算基本定律,3.2集合的运算及恒等式,除了以上的定律以外，还有一些关于集合运算性质的重要结果。,26,集合运算重要性质,3.2集合的运算及恒等式,证明一个集合为另一个集合的子集的基本思想是：设P,Q为集合公式，欲证，即证对于任意的x有成立。例3.1证明，即证明：对于任意x,27,集合运算重要性质,因此，,3.2集合的运算及恒等式,28,集合运算重要性质,3.2集合的运算及恒等式,29,集合运算重要性质,3.2集合的运算及恒等式,例3.4证明，即证明：,30,集合运算重要性质,因此,3.2集合的运算及恒等式,31,集合运算重要性质,集合的概念及其表示,集合的运算及恒等式,有穷集的计数和包含排斥原理,主要内容,3.3有穷集的计数和包含排斥原理,使用文氏图可以很方便的解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。一般来说，每一条性质决定一个集合，有多少条性质，就有多少个集合。如果没有特殊的说明，任何两个集合都画成相交的，然后将已知的元素个数填入该集合的区域内。通常从个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为，之后再根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。,33,3.3有穷集的计数和包含排斥原理,例3.9对24名会外语的科技人员进行掌握外语情况的调查，统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言（英、德、法、日）的人数和会三种语言的人数。解：令A，B，C，D分别表示会英