第3章-集合论.ppt

1、第二篇 集合论,集合论是现代各科数学的基础，它的起源可追溯到16世纪末期，那时为了建立微积分的可靠基础，人们对数集进行了研究。直到19世纪末，Cantor发表了一系列有关集合的论文，基本奠定了集合论的基础。不过，随后数学哲学中提出各种悖论，致使集合论的发展一度陷入困境。幸好不久，策墨罗(Zermelo)出现了，他提出了集合论的一整套公理体系，使数学哲学中所产生的悖论基本得到统一。从此集合论的发展进入飞速发展的时代。 第3章 集合 第4章 关系 第5章 函数。,题外话： 三个在数学发展中产生了巨大影响的悖论毕达哥拉斯悖论、贝克莱悖论、罗素悖论。 什么是悖论？笼统地说，是指这样的推理过程：它看上去

2、是合理的，但结果却得出了矛盾。 悖论是数学的一部分，在历史上曾为数学的发展提供了重要而持久的助推力。 一个悖论的数学本质被揭露了，它似乎就失去了被继续研究的价值。但是，在数学发展的历史上，它功不可没。,毕达哥拉斯是公元前五世纪古希腊的著名数学家与哲学家。他曾创立了一个合政治、学术、宗教三位一体的神秘主义派别：毕达哥拉斯学派。由毕达哥拉斯提出的著名命题“万物皆数”是该学派的哲学基石。而“一切数均可表成整数或整数之比”则是这一学派的数学信仰。然而，具有戏剧性的是由毕达哥拉斯建立的毕达哥拉斯定理却成了毕达哥拉斯学派数学信仰的“掘墓人”。,毕达哥拉斯定理提出后，其学派中的一个成员希帕索斯考虑了一个问题

3、：边长为1的正方形其对角线长度是多少呢？他发现这一长度既不能用整数，也不能用分数表示，而只能用一个新数来表示。希帕索斯的发现导致了数学史上第一个无理数2 的诞生。 一直到18世纪，当数学家证明了基本常数如圆周率是无理数时，拥护无理数存在的人才多起来。到十九世纪下半叶，现在意义上的实数理论建立起来后，无理数本质被彻底搞清，无理数在数学园地中才真正扎下了根。无理数在数学中合法地位的确立，一方面使人类对数的认识从有理数拓展到实数，另一方面也真正彻底、圆满地解决了第一次数学危机。,微积分这一锐利无比的数学工具为牛顿、莱布尼兹各自独立发现。这一工具一问世，就显示出它的非凡威力。许许多多疑难问题运用这一工

4、具后变得易如翻掌。但是不管是牛顿，还是莱布尼兹所创立的微积分理论都是不严格的。两人的理论都建立在无穷小分析之上，但他们对作为基本概念的无穷小量的理解与运用却是混乱的。因而，从微积分诞生时就遭到了一些人的反对与攻击。其中攻击最猛烈的是英国大主教贝克莱。 贝克莱悖论可以表述为“无穷小量究竟是否为0”的问题：就无穷小量在当时实际应用而言，它必须既是0，又不是0。但从形式逻辑而言，这无疑是一个矛盾。这一问题的提出在当时的数学界引起了一定的混乱，由此导致了第二次数学危机的产生。,下面仅举一无穷级数为例。无穷级数S11111到底等于什么？当时人们认为 一方面 S（11）（11）0；另一方面，S1（11）（

5、11）1，那么岂非01？ 这一矛盾竟使傅立叶那样的数学家困惑不解，甚至连被后人称之为数学家之英雄的欧拉在此也犯下难以饶恕的错误。他在得到1 + x + x2 + x3 + . = 1/(1- x) 后，令 x = 1，得出S1111112！由此一例，即不难看出当时数学中出现的混乱局面了 。,把分析重新建立在逻辑基础之上就成为数学家们迫在眉睫的任务。 经过数学家柯西，魏尔斯特拉斯、戴德金、康托尔各自独立深入的研究，终于从不同的角度建立起来的严谨的极限理论与实数理论，完成了分析学的逻辑奠基工作。数学分析的无矛盾性问题归纳为实数论的无矛盾性，从而使微积分学这座人类数学史上空前雄伟的大厦建在了牢固可靠

6、的基础之上。重建微积分学基础，这项重要而困难的工作就这样经过许多杰出学者的努力而胜利完成了。微积分学坚实牢固基础的建立，结束了数学中暂时的混乱局面，同时也宣布了第二次数学危机的彻底解决。,十九世纪下半叶，康托尔创立了著名的集合论，在集合论刚产生时，曾遭到许多人的猛烈攻击。但不久这一开创性成果就为广大数学家所接受了，并且获得广泛而高度的赞誉。数学家们发现，从自然数与康托尔集合论出发可建立起整个数学大厦。因而集合论成为现代数学的基石。“一切数学成果可建立在集合论基础上”这一发现使数学家们为之陶醉。1900年，国际数学家大会上，法国著名数学家庞加莱就曾兴高采烈地宣称：“借助集合论概念，我们可以建造整

7、个数学大厦今天，我们可以说绝对的严格性已经达到了。,可是，好景不长。1903年，一个震惊数学界的消息传出：集合论是有漏洞的！这就是英国数学家罗素提出的著名的罗素悖论。 設性質P(x)表示 ，現假設由性質P確定了一個類A也就是說 。 那麼現在的問題是： 是否成立？首先，若 ，則x是A的元素，那麼x具有性質P，由性質P知 ；其次，若 ，也就是說x具有性質P，而A是由所有具有性質P的類組成的，所以 。,理发师悖论：在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，

8、自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。,理发师悖论与罗素悖论是等价的： 因为，如果把每个人看成一个集合，这个集合的元素被定义成这个人刮脸的对象。那么，理发师宣称，他的元素，都是城里不属于自身的那些集合，并且城里所有不属于自身的集合都属于他。那么他是否属于他自己？这样就由理发师悖论得到了罗素悖论。反过来的变换也是成立的。,世界文学名著唐吉诃德中有这样一个故事： 唐吉诃

9、德的仆人桑乔潘萨跑到一个小岛上，成了这个岛的国王。他颁布了一条奇怪的法律：每一个到达这个岛的人都必须回答一个问题：“你到这里来做什么？”如果回答对了，就允许他在岛上游玩，而如果答错了，就要把他绞死。对于每一个到岛上来的人，或者是尽兴地玩，或者是被吊上绞架。有多少人敢冒死到这岛上去玩呢？,一天，有一个胆大包天的人来了，他照例被问了这个问题，而这个人的回答是：“我到这里来是要被绞死的。” 请问桑乔潘萨是让他在岛上玩，还是把他绞死呢？ 如果应该让他在岛上游玩，那就与他说“要被绞死”的话不相符合，这就是说，他说“要被绞死”是错话。既然他说错了，就应该被处绞刑。 但如果桑乔潘萨要把他绞死呢？这时他说的“

10、要被绞死”就与事实相符，从而就是对的，既然他答对了，就不该被绞死，而应该让他在岛上玩。 小岛的国王发现，他的法律无法执行，因为不管怎么执行，都使法律受到破坏。他思索再三，最后让卫兵把他放了，并且宣布这条法律作废。这又是一条悖论。,1908年，策梅罗（Ernst Zermelo)在自己这一原则基础上提出第一个公理化集合论体系，后来这一公理化集合系统很大程度上弥补了康托尔朴素集合论的缺陷。这一公理系统在通过Abraham Fraenkel的该进后被称为Zermelo-Fraenkel(ZF) axioms。在该公理系统中，由于限制公理（The Axion Schema of Comprehensi

11、on或Subset Axioms)：P(x)是x的一个性质，对任意已知集合A，存在一个集合B使得对所有元素xB当且仅当xA且P(x)；因此xx是一个集合并不能在该系统中写成一个集合，由于它并不是任何已知集合的子集；并且通过该公理，存在集合A=xx是一个集合在ZF系统中能被证明是矛盾的。因此罗素悖论在该系统中被避免了。,除ZF系统外，集合论的公理系统还有多种，如诺伊曼（von Neumann)等人提出的NBG系统等。在the von Neumann-Bernays alternative中，所有包含集合的collection都能被称为类(class)，因此某些集合也能被称为class，但是某些c

12、ollection太大了（比如一个collection包含所有集合）以至于不能是一个集合，因此仅仅是个class。这同样也避免了罗素悖论。 公理化集合系统的建立，成功排除了集合论中出现的悖论，从而比较圆满地解决了第三次数学危机。,不管一个数学问题叫不叫悖论，它总是一个问题。问题是数学的心脏，对问题的研究推动着数学的发展，对“悖论”的研究当然也会推动数学的发展。 把某些悖论的出现叫做数学危机，不知道是谁第一个说的。不过，多数数学家看来，数学没有危机，也不会有危机。但是数学家忙着自己的研究，一般不太关心数学危机的说法。研究数学哲学的人，对于有没有数学危机，也是各有不同的看法。但既然有了这个说法，又

13、比较能吸引大众的目光，让大家对数学有更多的兴趣，也是好事。,第三章 集 合,3.1 集合论基本概念 3.2 集合运算及其性质 3.3 集合的笛卡儿积与无序积,退出,3.1 集合论基本概念,1. 集合与元素 所谓集合，是指某些可辨别的不同对象的全体，或者说把具有一些确定的事物作为一个整体看待时，这个整体就是一个集合。集合是难于给出精确定义的一个概念，只能作上述形式的描述。 将用大写字母A，B，X，Y，表示之。组成集合的对象称为集合的元素或成员，将用小写字母a，b，x，y表示之。a是A的元素或a属于A，记作aA；a不属于A或a不是A的元素，记作aA，或者(aA)。,集合的元素一旦给定，这一集合便完

14、全确立。这一事实被形式地叙述为外延公理。 外延公理：两集合A和B相等，当且仅当它们有相同的元素。 若A与B相等，记为A=B；否则，记为AB。,外延公理可形式表为： A=B(x)(xAxB) 或者 A=B(x)(xAxB)(x)(xBxA) 顺便指出，在应用外延公理证明集合A与B相等时，只需考察： 对于任意元素x，应有下式 xAxB 成立即可。这就是说，证明两集合相等时可按此法行事。,集合的表示： 表示一个特定集合，基本上有两种方法： 一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。如 A=a,e,i,o,u (1) 表明集合A是由字母a, e, I ,o和u为元素构成的。

15、 B=1, 3, 5, (2),二是叙述法or谓词法. 用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素，确定了一个集合，因为这些元素都具有某种特殊性质。若P(x)含有一个自由变元的谓词公式，则x | P(x)定义了集合S，并可表为 S=x | P(x) 由此可见，P(c)为真当且仅当cS。从而有 xSxP(x),例如，(1)、(2)可表为 A=x | x是英文字母表中元音字母； B=x | x是正奇数。 在用性质来描述集合时，可表述为概括原理或子集合公理。 子集公理： 对于任给集合A和性质P，存在集合B，使得B中元素恰为A中满足P的那些元素。,子集公理可形式地表为 (B)(x)(x

16、BxA(x) 其中(x)为不含B自由出现。 子集公理的提出，避免了悖论，使集合论得以存在和发展。,应该指出的是：集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即a, a ,e, i, o, u= a, u, e, o, i。但有时对重复出现的元素都认为是集合的元素，这种集合称为多重集。即a, a, e, i, o, u, ua, e, i, o, u。 本书中集合在不特别指明时，都指前者，即中的集合。,集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。如，一本书，一支笔，集合1,2,3可以组成集合B=一本书，一支笔，1,2,3 。特别地

17、，以集合为元素的集合称为集合族或集合类如A=1,2,3, 8,9,6。 集合中元素之间可以有某种关联，也可以彼此毫无关系。,2. 子集、全集与空集 子集是描述一个集合与另一个集合之间的关系，其定义如下。 定义3.1.1 设A和B是任意两个集合，如果集合A的每个元素，都是集合B中的一个元素，则称A是B的子集，或称A被包含于B中，或者说B包含A，并记为AB。,本定义也可表成 AB(x)(xAxB) 这表明，要证明AB，只需对任意元素x，有下式 xAxB 成立即可。 此外，若集合B不包含集合A，记为AB。,/,定义3.1.2 设A和B是两个集合，若AB且AB，则称A是B的真子集，记为AB，也称B真包

18、含A。该定义也可表为 AB(ABAB),定义3.1.3 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为U或E。它可形式地表为 U=x|P(x)P(x) 其中P(x)为任何谓词公式。,显然，全集U即是第二章中的全总论域。于是，每个元素x都属于全集U，即命题(x)(xU)为真。由定义易知，对任意集合A，都有AU。 在实际应用中，常常把某个适当大的集合看成全集U。全集是个相对概念。,定义3.1.4 没有任何元素的集合，称为空集，记为，它可形式地表为： =x|P(x)P(x) 其中P(x)为任何谓词公式。 由定义可知，对任何集合A，有A。这是因为任意元素x，公式xxA总是为真。,注意，

19、与是不同的。是以为元素的集合，而没有任何元素，能用构成集合的无限序列： (1)， 该序列除第一项外，每项均以前一项为元素的集合。,(2)， 该序列除第一项外，每项均以前面各项为元素的集合。它即是冯诺依曼在1924年使用空集给出自然数的集合表示： 0:=，1:=，2:= ,， 定理3.1.1 空集是唯一的 定理3.1.2 ()对任一集合A，有AA。 ()若AB且BC，则AC。 对任何一个集合A: A和称为A的两个平凡子集。,3集合的基数 表示集合中元素多少或度量集合大小的数，称作集合的基数或势。一个集合A的基数，记为|A|。 如果一个集合恰有m个不同的元素，且m是某个非负整数，称该集合是有限的或

20、有穷的，否则称这个集合为无限的或无穷的。例如，在本书中常用有穷集有： Nm=0,1,2,m-1,本书中常见的无穷集合有： N=0,1,2,3,，即自然数集合。 Z=,-2,-1,0,1,2,3,，即整数集合。 Z+=1,2,3,，即正整数集合。 Q=有理数集合。 R=实数集合。 C=复数集合。,4集合的幂集 一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族。 定义3.1.5 设A为一集合，A的幂集是一集合族，记为P(A)， P(A)=B|BA 由定义可知，P(A)，AP(A)。 若|A|=n, 则|P(A)|=2n,5文氏图 文氏(Venn)图是一种利用平面上的点构成的图形

21、来形象展示集合的一种方法。全集U用一个矩形的内部表示，其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。,如果AB，则表示A的圆面一般将完全落在表示B的圆面内，如图1中(a)。如果A与B没有公共元素，那么表示A的圆面将同表示B的圆面分开，如图3-1中(b)。当A和B是两个任意的集合时，可能会是：有些元素在A中但不在B中，有些元素在B中却不在A中，有些元素同时在A和B中，有些元素则既不在A中也不在B中，因此用图1中(c)表示任意两个集合A和B。,图 3-1,最后给出集合的形式定义结束本节。 定义3.1.6 A为集合=(x)(xAA=)。 这里等号“=”表示定义为的意义，是表示“定义为”还是表示

22、“一般相等”的意义，由上下文来区分。,3.2 集合运算及其性质,集合运算是指用已知的集合去生成新的集合。假设所有集合都是全集U的子集，即这些集合是利用子集公理得到的。下面依次介绍常见的集合运算。,1并、交和差运算 定义3.2.1 设A和B是任意两个集合， A和B的并是集合，记为AB， AB=x|xAxB A和B的交是集合，记为AB， AB=x|xAxB A和B的差，或B关于A的相对补是集合，记为A-B， A-B=x|xAxB,定义3.2.2 若A和B是集合，且AB=，则称A和B是不相交的。 如果C是个集合族，且C中任意两个不同元素都不相交，则称C中集合是两个不相交的，或称C是两两不相交的集合族

23、。,定理3.2.1 任给集合A，B和C，则： AB=BA AB=BA (AB)C=A(BC) (AB)C=A(BC) 该定理表明，集合并和交运算满足交换律和结合律。,定理3.2.2 任给集合A、B和C，则 A(BC)=(AB)(AC) A(BC)=(AB)(AC) 该定理表明，集合运算并对交、交对并都是可分配的。,定理3.2.3 任给集合A，B，C和D，则 若AB，则AB=B，AB=A 若AB和CD，则ACBD，ACBD,推论3.2.3 AU=U，AU=A 定理3.2.4 任给集合A，B和C，则 A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C),定义3.2.3 设A是含有

24、元素为集合的集合，或者集合族。 A的并是集合，记为A， A=x|(B)(BAxB)= B A的交是集合，记为A， A=x|(B)(BAxB)= B,B A,B A,定义3.2.4 集合A的补是集合，记为A， A=U-A=x|xUxA =x|xA 这里称为绝对补。相对补是指A-B称为B相对于A的补集。 定理3.2.5 任给集合A，则 AA=U， AA=。,定理3.2.6 任给集合A和B，则 B=A iff AB=U 且 AB= 该定理表明了若A的补是B，则B的补是A，即A和B互补。补的唯一性。 推论3.2.5 U=，=U 定理3.2.7 任给集合A，则(A)=A。 该定理表明了，A的补的补是A。

25、,定理3.2.8 (德摩根律) 任给集合A和B，则 (AB)=AB， (AB)=AB。 定义3.2.5 任给集合A和B，A和B的对称差是集合，记为AB， AB =(A-B)(B-A) =x|(xAxB)(xBxA),定理3.2.9 任给集合A和B，则 AB=(AB)(AB) =(AB) - (AB) 推论3.2.9 AB=AB AB=BA AA=,2集合代数与对偶原理 本小节将形式地讨论由集合、集合变元、集合运算和圆括号所构成的集合代数以及集合代数中的对偶原理。 与命题逻辑相似，对于给定集合实行集合运算，可以生成新的集合。同用大写英文字母表示确定集合一样，也用大写字母表示不确定的集合，前者称为

26、集合常元，后者称为集合变元。集合变元用以集合常元代替后，才表示确定的集合。下面将给出集合的合式公式定义。,定义3.2.6 可按下列规则生成集合合式公式： 单个集合变元是集合合式公式。 若A是集合合式公式，则A也是集合合式公式。 若A和B是集合合式公式，则(AB)，(AB)，(A-B)和(AB)也都是集合合式公式。 只有有限次使用、和构成的符号串才是集合合式公式。 为方便计，简称集合合式公式为公式。,定义3.2.7 用任意集合常元取代两个集合公式中的各个集合变元，若所得集合是相等的，则称该二集合公式是相等的，简称等式。 因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合恒等式，或集合定律。它们刻划了集合运算的某些性质，这些性质描述一个代数，称为集合代数。下面列出常用集合定律：,（1）等幂律AA=A AA=A （2）结合律 (AB)C=A(BC) (AB)C=A(BC) （3）交换律 AB=BA AB=BA （4）分配律 A(