集合论-第四章.pptVIP

例2 理发师悖论是Russell在1918年给出的，一个乡村理发师公开宣布他不给村子中所有自己替自己理发的人理发，但却给所有自己不替自己理发的人理发。 一天他发生了疑问，他是否应当给自己理发。 如果他自己替自己理发，那么按他声言的前半部分，他就不应当给自己理发； 如果他的头由另外的人给他理，那么按照他的规定，他又必须给自己理发。 理发师的头应由谁来理呢？这个理发师陷入了逻辑的窘境。 Russell悖论是相当简单的，一点也用不到集合论的专门知识。 例3 Russell仔细地分析了Contor给集合下定义： “把一些确定的，可以区别的事物——可以是直观的对象，也可以是思维的对象——放在一起，组成一个整体，称为集”，他发现集合可以分成两种: 第一种是集合Ａ本身不是Ａ的一个元素，即A?A； 第二种是集合Ａ本身是Ａ的一个元素，即A∈A。 可以看出：对任意的一个集A，不是第一种就是第二种，两种集彼此可以明确识别，所以由Cantor的定义，令 S={A|A?A}, 也就是说Ｓ是由满足条件“A?A”的那些Ａ组成的一个新的集合，现在我们要问： 集合S是第一种集还是第二种集？即A?A，还是A∈A。 若S是第一种集，即S?S； 因为Ｓ是由所有满足条件的A?A组成的，而S?S，知S当然就在S中，也就是说S∈S。而S∈S，表明S是第二种集，从而产生矛盾。 若Ｓ是第二种集，即S∈S； 因为对S中任一元素A，都有A?A，而S∈S，知S是S中的元素，也就是S?S。而S?S，表明Ｓ是第一种集，从面产生矛盾。 这样，Ｓ既不是第一种集也不是第二种集，即Ｓ既不是S?S，也不是S∈S。 这个矛盾就是Russell所发现的“集合论是自相矛盾的”，即著名的Russell悖论。 例4 Cantor最大基数悖论 Cantor在1899年给出的悖论，现叙述如下： 集合是具有某些性质的元素组成，因此也可以假设集合Ｓ是由所有集合所组成的集合。现在要问： S与2S的基数哪一个基数更大。 这个悖论称为Contor最大基数悖论。 一方面，由Cantor定理可知，|S||2S|。 但另一方面，因为S是所有集合所组成的集合，而2S中每个元素都是S的一个子集，从而2S是集合，所以2S?S，即|2S||S|。于是产生了矛盾。 但是，Cantor的最大基数悖论并未引起人们多大的注意，因为它涉及的概念较多： 集，子集，基数，基数之间的大小比较等。 人们认为可能是由于某些中间环节技术处理得不恰当所引起的。当时Cantor想对集合加以区分，借以排除他的悖论，但他的悖论尚未排除， Russell悖论又出现了，而Russell悖论是从集合论的基本概念着手的，它是那样的那初等，那样清晰明白不容辩驳，人们不得不承认，集合论自相矛盾。 5.2悖论的所在 现在我们要问问题的毛病出在哪里呢？ 由Russell悖论可以得出，问题就出在Cantor对集合概念的定义上。这个定义蕴含着矛盾，蕴含着循环定义。 集合是由元素组成的，在集合还未形成时怎能以一个实体出现充当自己元素呢？这不正是含有循环定义吗？ 因此，在对集合概念描述时，曾强调不能说 “所有集合的集合” 这样一类话的原因。 5.3解决方法 为了解决集合论的悖论，为了解决集合论中自身的问题，一些著名数学家在本世纪初开始了集合论公理化方面的研究，产生了各种不同的学派和各种不同的公理系统，解决了悖论问题，大大推进了集合论的发展，有关集合论公理化方面的内容，本书作为自学介绍，有兴趣读者请参看有关文献。 本书是以朴素的观点来介绍集合论的，因此未给出公理系统，但对于计算机科学的一般问题以及大多数数学问题及其应用，这已足够了。 总 结 可数集合、连续统、无穷集合 基数、基数的比较 对角线法的应用 定理 { [0,1]不可数 ；|A||2A|} 2013年. 1.某校学生参加数学、物理、英语三科竞赛，某班30名学生中有15人参加了数学竞赛，8人参加了物理竞赛，6人参加了英语竞赛，并且其中3人三科竞赛都参加了，问至少有多少人一科竞赛都没有参加。 （a）7； ( b）8；（c）9；（d）10。 2.设f:N×N→N,f((x,y))=x?y。则f是单射、满射或双射？ (a)f既是单射也是满射，即双射； (b)f既不是单射也不是满射； (c)f是单射但不是满射； (d)f不是单射但是满射。 3. 设N={0,1,2,3,…},f:N→N, g:N→N,f(n)=n+1, g(n)=max{0,n-1}，I是自然数集合N上的恒等映