大连理工大学软件学院 离散数学 第三章 集合论-1st

《大连理工大学软件学院 离散数学 第三章 集合论-1st》由会员分享，可在线阅读，更多相关《大连理工大学软件学院 离散数学 第三章 集合论-1st（39页珍藏版）》请在金锄头文库上搜索。

1、1/39第三章 集合论2/39回顾6个逻辑联接词 最小完备运算集 命题变元、命题公式 永真式、永真蕴含 代入规则、替换规则 永真、永假、可满足 对偶 三个原理/定理 范式 基本和、基本积、极小项、极大项 析取、合取 主析取、主合取 命题的翻译 推理四规则 P规则 T规则 CP规则 F规则3/39回顾 个体、谓词、量词 全称量词、存在量词 自由变元、约束变元 谓词公式、谓词公式的解释 含量词的等价式和永真蕴含式 量词转化律、扩张及收缩律、量词分配律 谓词公式的翻译 推理规则 约束变元改名 自由变元代入 取代规则 量词的增删规则 全称特指（Universal Specification） 存在特指

2、（Existential specification） 存在推广（existential generalization） 全称推广（universal generalization）4/39集合论的创立与康托尔的遭遇19世纪末期，数学界出现了一件引人注目的事情。一位 名叫康托尔（G.Cantor， 18451918）的德国数学家提出一 种令人费解的古怪理论-集合论。它的内容是如此与常识 格格不入，以致于一出世就引起了一场轩然大波。 自从17世 纪牛顿和莱布尼茨）创立微积分理论体系之后 ，在近一二百年时间里，微积分理论一直缺乏一个严格的逻 辑基础。它的一些基本概念的表述，还有某些混乱和自相矛 盾

3、之处。从19世纪开始，柯西、魏尔斯特拉斯等人进行了微 积分理论严格化的工作。他们建立了极限理论，并把极限理 论的基础归结为实数理论。那么，实数理论的基础又该是什 么呢？康托尔试图用集合论来作为实数理论，以至整个微积 分理论体系的基础。 5/39出于这一目的，康托尔用集合的观点重新考察各种数 量关系，特别是无穷数量关系。 他发现，无穷集合有着有 穷数量关系所不具备的性质。比如，在无穷集合领域，所 有整数和所有偶数之间是一一对应的，所有有理数和所有 整数之间是一一对应的，平面上所有的点和线段上所有的 点是一一对应的，概言之，在无穷的世界里，整体的 所有元素和部分的所有元素之间可以是一一对应的。另外

4、 ，无穷集合并不都是相等的，比如所有实数和所有有理数 之间就不是一一对应的。因而，无穷集合是有大小的。集 合论用“基数”这个概念来表示无穷集合间的区别。那么，有没有一个最大的集合呢？康托尔通过研究， 否定了这个想法。因为每个已知集合的所有子集所构成集 合，其基数都大于已知集合的基数。既然没有最大的基数 ，当然也没有最大的集合。无穷世界里的这些性质， 初 看起来，真是令人头晕目眩。6/39康托尔的研究成果发表之后，马上遭致当时一些 赫赫有名的数学家的激烈攻击。德国数学家克隆尼克 是这些人中言辞最激烈、攻击时间最长的一个。克隆尼克比康托尔年长22岁。他主张，除非一种 数学对象能够用有限步骤从自然数

5、中构造出来，否则 不能认为它在数学上是存在的。他有一句“名言”： “上帝创造了自然数，其余的一切才是人做的工作” 。因此，他否认无理数的存在，也否认极限理论的意 义。虽然康托尔是他的学生，但由于集合论的内容同 他的主张大相径庭，所以克隆尼克简直到了不能容忍 的程度。他认为，康托尔关于超限数的研究，是一种 非常危险的数学疯病。克隆尼克的影响还使康托尔的 学术论文一再延误发表日期。7/39除了克隆尼克之外，还有一些著名数学家也对 集合论发表了反对意见。法国数学家彭加勒说：“我个人，而且还不只我 一人，认为重要之点在于，切勿引进一些不能用有 限个文字去完全定义好的东西”。他把集合论当作 一个有趣的“

6、病理学的情形”来谈，并且预测说： “后一代将把（Cantor）集合论当作一种疾病，而 人们已经从中恢复过来了”。德国数学家魏尔认为，康托尔关于基数的等级 观点是雾上之雾。菲利克斯克莱因也不赞成集合论的思想。数学家HA施瓦兹原来是康托尔的好友，但他 由于反对集合论而同康托尔断交。8/39尽管有希尔伯特等著名数学家赞同他的集合论 ，尽管他的集合论事实上已取得巨大的成功，仍未 能使康托尔感到欣慰和满足。从1884年春天起，即在他40岁的时候，他患了 严重的忧郁症，极度沮丧，神态不安。不过，在精 神病发作的间歇阶段，康托尔仍然顽强地坚持集合 论的研究。而且当每次从精神病发作中恢复过来的 时候，他都感到

7、自己的脑子变得格外清晰。他在集 合论方面许多非常出色的成果，都是在精神病发作 的间歇时期获得的。然而，长期的精神折磨所造成 的危害毕竟是不容忽视的。由于健康状况逐渐恶化 ，1918年，他在哈勒大学附属精神病院去世。 9/39公理化集合论的建立到二十世纪初集合论已得到数学家们的赞同。数 学家们为一切数学成果都可建立在集合论基础上的前 景而陶醉了。他们乐观地认为从算术公理系统出发， 借助集合论的概念，便可以建造起整个数学的大厦。 在1900年第二次国际数学大会上，著名数学家庞加莱 就曾兴高采烈地宣布“数学已被算术化了。今天 ，我们可以说绝对的严格已经达到了。”然而这种自得的情绪并没能持续多久。不久

8、， 集合论有漏洞的消息迅速传遍了数学界。这就是 1902年罗素得出的罗素悖论。10/39罗素构造了一个所有不属于自身（即不包含自 身作为元素）的集合R。现在问R是否属于R？如果R属于R，则R满足R的定义，因此R不应属 于自身，即R不属于R；另一方面，如果R不属于R ，则R不满足R的定义，因此R应属于自身，即R属 于R。这样，不论何种情况都存在着矛盾。这一仅涉及集合与属于两个最基本概念的悖论 如此简单明了以致根本留不下为集合论漏洞辩解的 余地。绝对严密的数学陷入了自相矛盾之中。这就 是数学史上的第三次数学危机。11/391908年，策梅罗提出公理化集合论，后经改进 形成无矛盾的集合论公理系统，简

9、称ZF公理系 统。原本直观的集合概念被建立在严格的公理基 础之上，从而避免了悖论的出现。这就是集合论 发展的第二个阶段：公理化集合论。与此相对应 ，在1908年以前由康托尔创立的集合论被称为朴 素集合论。公理化集合论是对朴素集合论的严格处理。 它保留了朴素集合论的有价值的成果并消除了其 可能存在的悖论，因而较圆满地解决了第三次数 学危机。 12/39主要内容 集合的概念与表示方法 集合的基本运算 包含与排斥原理 多重序元 迪卡尔乘积13/3914/393.1集合的概念及其表示集合是由某些特殊对象汇集在一起构成的集合是由某些特殊对象汇集在一起构成的。一般 来说这些对象具有某种共同的性质。 组成集

10、合的那些个体称为集合的元素元素。 全体中国人 全部整数 全国的高校 全部叫李明的人 用大写字母表示集合（如A），小写字母表示集 合中的事物（如a） 若个体a是集合中A的元素，记作“aA” 若个体a不是集合中A的元素，记作“a A”一、集合和元素集合数学中集合论论的研究对对象。 A collection of well defined and distinct objects15/39一、集合和元素注意：集合中的元素也可以是集合。16/39二、集合的表示方法（1）枚举法：把集合中的元素写在一个花括号内 ，元素间用逗号隔开。例如：A=2,a,b,9,B=4,5,6,7,8（2）构造法：构造法又叫谓

11、词法。如果P(x)是表 示元素x具有某种性质P的谓词，则所有具有性 质P的元素构成了一个集合，记作A=x|P(x)。例如：集合B可以表示成B=a|a N且4a8D=2xxZ且x50,即D=0,2,4,6,98,10017/39二、集合的表示方法几个常见的集合的表示符号： N：所有正整数的集合。 Z：所有非负整数的集合。 R：所有实数的集合。 I：所有整数的集合。 Q：所有有理数的集合。 P：所有素数的集合。 Nm：从1到m，这m个正整数的集合。 Zm：从0到m-1，这m个非负整数的集合。18/39小插曲23,29,31,37.下一个数是什么？3,5,8,13,21,( )19/39三、集合的外

12、延和内涵 符合某个概念R的那些客体的集合A，叫作该概念R 的外延外延；集合A中诸客体共有的本质属性P(x)，叫作 该概念R的内涵内涵。 外延：所有人的集合 人 内涵：人所共有的本质属性（外貌、思想等） 一个概念的外延越大，则内涵越小。（人，黄种人 ） 外延性原理：两个集合相等，当且仅当它们有相同 的元素。记作A=B 20/39四、集合的基数 集合A中不同元素的个数叫集合A的基数，记 作#A 或|A|。 例如：A=2,3,4, #A=3， A为有限集.A=x|x Z, #A无穷大， A为无限集.，#S=4.五、空集 不包含任何元素的集合为空集，记作 。 例如：A=x | xR 且 x2+8=0

13、=注意： 与 的区别21/39六、集合之间的关系1.集合的相等定义：若A、B是两个集合，当且仅当A、B两集合 恰恰有完全相同的成员时，称A、B两集合相等，记 作A=B。例如：设A=x | xN 且 x能整除24， B=1, 2, 3, 4, 6, 8, 12, 24 则 A=B注意注意： 1.集合中不考虑重复元素。例如：1,2,3=1,2,2,3.2.集合中不考虑元素的排列顺序。例如：1,2,3=3,2,1.3. 1,2,3 1,2,3.22/39六、集合之间的关系2.集合的包含定义：定义：设有集合A、B，如果A的每一个元素都是B 的元素，则称A是B的子集或B是A的包含集，记 或 。例如：可以

14、得出注意：注意：若 ，则有23/39集合的包含关系应具有以下性质：(1)对任意集合A，都有 (2)对任意集合A，都有 (3)对任意集合A、B， (4)对任意集合A、B、C，若 ，那么证明: (1)（反证法） 假设 是假，则至少有一个 元素x，使得 且 ，然而这与空集不包含任 何元素相矛盾，所以以上假设不成立，即为真。 A的平凡子集24/39六、集合之间的关系3.集合的真包含定义：如果集合A的每一个元素都属于B，但集合B中 至少有一个元素不属于A，则A称为B的真子集，或A 真包含于B，记作 。例如：设A=0，1，B=0，1，2，C=0则25/39七、全集定义： 在一定范围内，如果所有集合均为某一

15、 集合的子集，则称该集合为全集，记作E。举例：全集的概念相当于论域，如在初等数论 中，全体整数组成了全集。UAAB26/39八、幂集定义：给定集合A，由集合A的所有子集为元素组 成的集合称为集合A的幂集，记为 。例： 设A=a 1个元素的子集：a则0个元素的子集： 设B=a,b 1个元素的子集：a,b 2个元素的子集： a,b 则0个元素的子集： 设C=a,b,c 1个元素的子集：a,b,c 2个元素的子集：a,b,a,c,b,c3个元素的子集：a,b,c 则0个元素的子集： ；27/39九、幂集定理：如果有限集合A有n个元素，则它的幂集有2n个元 素。 证明：A的所有k个元素组成的子集数为从n个元素中取k个的组合 数。 另外， 因为 ，因此 的总数N可表示为因为 令x=y=1，得故集合A的幂集的元素个数为2n28/39幂集的编码表示以S=a,b,c为例说明可得29/393.2集合的运算定义：由集合A和B的所有公共元素所组成的集合 ，称为集