《集合论语形悖论精选文档.ppt》由会员分享，可在线阅读，更多相关《集合论语形悖论精选文档.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、集合论语形悖论本讲稿第一页，共三十八页一、罗素悖论一、罗素悖论1901年6月，罗素在利用康托儿的集合论解决问题时，发现了罗素悖论，在1902年罗素写信把这个反先告诉了弗雷格，使得弗雷格大为震惊，在算术基本法则中，弗雷格尝试用集合概念来定义数，并认为这一任务已大致完成。然而在这个时候，他得知了所谓的“罗素悖论”，这一悖论对弗雷格的事业是一个毁灭性的打击。本讲稿第二页，共三十八页弗雷格在他的算术基本法则第二卷的结尾处写了这样的一段话：“一个科学家工作完成之日，也是这一建筑物的几处倒塌之时，没有什么比这个更糟糕了。当本书即将付梓之时，罗素先生的一封信把我置于这样的境地。”“在工作已经结束时，自己建造
2、的大厦的一块主要基石却动摇了，对一个科学家来说，没有比这更让人沮丧了”。弗雷格以一个学者对于理论和研究的深刻忠诚，承认了这一切，1902年，弗雷格在算术基础第二卷“后记”中将该悖论随书出版公布。本讲稿第三页，共三十八页什么是罗素悖论呢？这就是罗素发现的在近代由康托儿提出的集合论中间包含着的一个悖论。在素朴集合论中，集合本身也能够成为集合的元素和对象，但是集合本身能否成为自己身的元素和对象呢？有些集合本身还可以成为自己集合的一个对象，例如，元素个数不为3的集合，记作元素个数不为3，本讲稿第四页，共三十八页元素个数不为3的集合有很多，肯定不是只有3个，所以这个集合元素个数不为3，即元素个数不为3的
3、所有的集合本身构成的集合，它的元素个数肯定不是3，那么它也应该属于元素个数不为3的集合。这样的集合我们称之为是属于自身的集合，记作属于自身的集合，即所有那些和上例相同的，能够属于自己的集合放在一起构成的大的集合。本讲稿第五页，共三十八页当然与这个相对还有另一种情况：即集合是不属于自身，例如人这个集合，集合里的元素就是世界上个人，而由人构成的集合本身只是一个集合，肯定不是人，所以它就不能属于自己。而由这样的集合不属于自身的集合，放在一起构成一个集合，这个集合就是不属于自身的集合的集合，记作不属于自身的集合。本讲稿第六页，共三十八页我们就把所有的集合分为了两种情况：属于自身的和不属自身的，而两种不
4、同性质的集合又分别构成了两个大的集合，即属于自身的集合；不属于自身的集合。这样两个集合我们分别用逻辑符号表示为：x属于x；x不属于x对于这两个新的集合：属于自身的集合和不属于自身的集合他们本身又是否属于自身呢？属于自身的集合，很明显它是属于自身的，本讲稿第七页，共三十八页因为属于自身的集合，它本身就是一个属于自身的集合，当然按照对集合的两种归类，它应该被归到属于自身那一类，所以它是属于自身的，即属于自身的集合属于属于自身的集合，即它是属于自身的，逻辑符号可以记作：x属于x属于x属于x；但是对于集合不属于自身的集合，如何判断它呢？就是说这个集合是属于自身还是不属于自身，这就是罗素悖论的来源。本讲
5、稿第八页，共三十八页弗雷格表述如下：“为简短起见，我们称之为类K。现在让我们问，这个类K是不是属于自身。如果一个东西属于一个类，那么它就归属于以这个类为其外延的概念。这样，如果类K属于自身，那么它就是一个不属于自身的类。因此我们的第一个假定导致自相矛盾。第二，让我们假定类K不属于自身，这样它就属于以自身为其外延的概念，因此就属于自身。这里我们又一次得到同样的矛盾。”本讲稿第九页，共三十八页这里解释两点：第一，“以这个类为其外延的概念”，这里“一个概念是一个其值总是一个真值的函数”，即命题函项。例如人这个概念指的是X是人这个函数，某物归属于这个概念，即它可以满足X是人这个函数式（使之为真）。第二
6、，集合的内涵和外延。本讲稿第十页，共三十八页第一步，我们假设它是属于自身的；假设这个集合是属于自身的，即它是集合不属于自身的集合的一个元素，而集合不属于自身的集合的元素具有什么特点呢？即不属于自身，既然我们假定它是属于这个集合的，是这个集合的一个元素，当然它也应该具有这个性质：不属于自身，这样我们经过推倒得到的结论就是：它不属于自身。而这个结果就和假设相矛盾了；第一步的假设不成立。本讲稿第十一页，共三十八页第二步，我们假定它不属于自身；假设这个集合不属于自身，不就意味着集合不属于自身的集合不属于不属于自身的集合，由于这个集合不属于自身，按照对于集合的两个划分，要么属于自身，要么不属于自身，而它
7、不属于自身，因此就应该被归到不属于自身那一类，即属于集合不属于自身的集合，由于它属于集合不属于自身的集合，即集合不属于自身的集合属于不属于自身的集合，而这样它 不就又属于自身了，而这与我们的假定正好矛盾。第二步假设也不成立。本讲稿第十二页，共三十八页通过两个假定，我们都得出了矛盾，两个假定都出了问题，就是说对于集合不属于自身的集合，我们既不能说它属于自身，也不能说它不属于自身，这不就等于说它本身无法处理了。如果我们把集合不属于自身的集合记作A，则我们不就得到这样的结果：假定A是A，则A不是A，假定A不是A，则A 是A，因而这就是一个悖论。如果用逻辑符号表达，设x不属于x记作A，如果A属于A，把
8、带入集合，得到不属于；如果不属于，根据集合定义，不属于属于集合x不属于x，则属于，于是悖论。本讲稿第十三页，共三十八页理发师悖论；理发师悖论；在一个小村庄，一个理发师挂出一块招牌，写到：“我给且仅给不给自己理发的人理发！”那么，他是否应该给自己理发呢？如果理呢，则他明显给自己理发了，按照规定他不能给自己理发；不过不理呢，它属于那些不给自己理发的人，他应该给自己理发；怎么办？通俗版本通俗版本本讲稿第十四页，共三十八页我跟且跟不与自己聊天的人聊天！本讲稿第十五页，共三十八页二、最大序数悖论二、最大序数悖论1895年，康托尔发现了最大序数悖论，1897年公开发表。最大序数悖论构建过程中使用的概念比较
9、多，人们总认为其推导过程中一定存在着尚未被发现的漏洞，因而没引起什么危机感。罗素悖论的力量则在于它的极端简洁性。本讲稿第十六页，共三十八页如果一个集合的任何两个元素之间，都按确定的次序关系排列，则称该集合为序集。其中次序关系为不自返、不对称而传递关系。如果一个序集的任一非空子集，都有一个在给定次序下的最初元素，则称此集合为良序集。例如集合S=1,2,3，是良序集，S1=-3,-2,-1,0,1,2,3,是序集但非良序集。明显，任一有限集都是良序集。本讲稿第十七页，共三十八页如果两个序集的全部元素都能一一对应，而且相应元素的次序关系相同，则称这两个集合相似。任意两个或多个集合之间具有相似关系，则
10、称它们具有相同的序型。序数就是指良序集的序型。现在看下从小到大的自然数集0,1,2,3，n，。显然，0之后的每一个数都是它前面的数构成的数集的序数，而0代表空集的序数。换言之，自然数集代表了所有有限序数。由所有有限序数可构成一良序的无限集合。本讲稿第十八页，共三十八页在无限集合中，康托把由小到大的自然数集合作为最简单无限良序集，把它记做w，w称为第一个超限序数。w之后紧接着的第一个序数记为w+1，它是良序集0,1,2,，n,0的序型。之后可得w+2，w+3,，再之后是2w，2w+1，由此继续推进，康托尔把所有序数的集合本身构成一个良序集，其中每个序数都是描述在它之前的序集的序型。本讲稿第十九页
11、，共三十八页现在设定一个所有序数的集合O，明显所有的序数集合也是一个良序集，它也应该有一个序数，那么是不是O的元素？既然是一个序数，那就应当作为所有序数的集合O的元素；但由于是O本身的序数，根据序数理论，每一个良序集的序数都应该大于该集合的所有元素，它有应当大于O的任一元素，因而又不应是O的元素。于是，上述超序数理论导致了矛盾。本讲稿第二十页，共三十八页康托尔反复探讨未能解决这个问题，于是写信请求希尔伯特共同探讨。他们都认为经过某个枝节的修正就能解决问题。三、布拉里三、布拉里-弗蒂悖论弗蒂悖论后来意大利学者布拉里-弗蒂在1897年独立发现这一问题，并将之公开发表，以下是罗素对布拉里-弗蒂的转述
12、，内容如下：“可以证明，每个良序集的序列都有一个序数，达到并包含任意给定序数的序列比给定的序数要多出一个，并且所有序数的序列式良序的。本讲稿第二十一页，共三十八页由此可以得出：所有序数的序列有一个序数，比如说。但是这种情形下，所有的序数的序列有序数+1，而这必定大于，因而不是所有序数的序数。”当时学界对待这个悖论与康托尔悖论的态度是一致的。但通过类似于罗素悖论的推导过程很容易得到矛盾等价式：是O的元素，当且仅当，不是O的元素。相对于前述素朴集合论，此处得到的是严格意义的逻辑悖论，史称“布拉里-弗蒂悖论”本讲稿第二十二页，共三十八页四、格瑞林悖论 1908年纳尔逊和他的学生格瑞林把下面的悖论发表
13、出来。如果一个形容词所表示的性质适用于这个形容词本身，比如“黑的”这两字的确是黑的，那么这个形容词称为自适用的。反之，一个形容词如果不具有自适用的性质，就叫做非自适用的。例如“英语的”三字本身是汉语写成的，就不是自适用的。本讲稿第二十三页，共三十八页现在我们来考虑非自适用的这个形容词，它是自适用的还是非自适用的呢?如果“非自适用的”是非自适用的，那么它就是自适用的；如果“非自适用的是自适用的，那么按照这词的意思，它是非自适用的，这就导出矛盾。本讲稿第二十四页，共三十八页五、悖论的影响五、悖论的影响十九世纪末及二十世纪初，数学空前兴旺发达，十九进纪七十年代康托创立的集合论是现代数学的基础，素朴集
14、合论已被证明可以作为算数乃至整个数学大厦的基础。罗素悖论的出现直接导致了基石的动摇，产生了第三次数学危机。本讲稿第二十五页，共三十八页六、悖论的解决六、悖论的解决（一）、类型论（一）、类型论简单类型论简单类型论限制“属于”符号的应用，对每一个集合规定其类型，当且仅当“属于”号后面的类型比前面的类型大于1时，“属于”的运用才有意义。本讲稿第二十六页，共三十八页分支类型论分支类型论处理谓词对任一性质按照它处理的对象进行分类；个体属于0级谓词；谓词处理的对象是个体称为1级谓词；谓词处理的对象是1级谓词或者个体，且至少有一个1级谓词称为2级谓词；本讲稿第二十七页，共三十八页谓词处理的对象都是n级以下谓
15、词，且至少有一个n级谓词称为n+1级谓词。规定每一等级谓词不能处理该谓词的对象总体以及更高等级的谓词，每一谓词的应用只有在低于其等级的谓词对象时才有意义；凡是涉及一个谓词对象整体的对象不能属于该整体。罗素悖论探讨对象全体是否属于本身，这种探讨不合规定；本讲稿第二十八页，共三十八页（二）、公理化集合论（二）、公理化集合论1908年，策墨罗提出了第一个构造公理化集合论系统解决集合论悖论的完整方案。策墨罗把矛头指向“任一特征属性可决定一集合”这个概括原则，他认为集合并不是任意特征属性都可决定的汇合，而是必须满足某些存在条件的对象。集合的存在性经由几条他精心研究而提出的几项公理加以保证：本讲稿第二十九
16、页，共三十八页（1）确定性公理：每一集合都由它的元素唯一决定。（2）基本集合存在公理：空集存在，单元素集合存在，对偶集存在。（3）分出公理：如果谓词P对已知集合B中的所有元素都由意义，则可以从B中分出一个子集A，而A由B中所有满足谓词P的元素组成。（4）幂集公理：每一集合存在一幂集。（5）并集公理：任一集合的所有元素的元素组成一集合。本讲稿第三十页，共三十八页（6）无限公理：至少存在一集合，空集是它的元素，且如果x是它的元素，x也是它的元素。（7）选择公理：若A是由不相交的非空集合组成的集合，则存在一集合，它和A的每一个元素恰有一共同元素。弗兰克尔增加了公理（8）替换公理：若f是一个函数，对一
17、个已知集合中的任一元素x而言，f（x）也是一个集合，那么，所有这些f（x）就构成一个新的集合。本讲稿第三十一页，共三十八页1925年，冯诺依曼提出了（9）增加公理：对任一没空集合，一定有这样的元素存在，它与原来的集合没有公共元素。于是，以一阶逻辑和唯一的谓词符号属于，通过公理（1）（9）为基础构建的公理化集合论，既可以起到康托尔作为数学基础的作用，又消除了集合论悖论，新的悖论也没有产生。一般人们把除了选择公理之外的其它公理被称为ZF系统，把包含选择公理的系统成为ZFC系统；而康托尔的集合论被称为素朴集合论。本讲稿第三十二页，共三十八页康托尔悖论直接来自于素朴集合论中如下两个论断的矛盾：（1）存
18、在大全集，即存在以一切集合为自己的元素的集合；（2）任何集合都有幂集，即一切集合都可扩充到一个以它为元素的更大的集合。ZF系统放弃了（1）解决悖论。本讲稿第三十三页，共三十八页七、哥德尔不完全定理七、哥德尔不完全定理哥德尔不完全定理是20世纪前30年集合论-语形悖论研究热潮的终结，也是这次研究热潮所取得的最大成就。哥德尔也因此被誉为继亚里士多德之后最伟大的逻辑学家。数学史家伊夫斯曾把哥德尔不完全定理的学术价值概括为如下四方面：（1）它推翻了数学的所有重要领域能被完全公理化这个强烈的信念；本讲稿第三十四页，共三十八页（2）它摧毁了沿着希尔伯特曾设想的路线证明数学内部相容性的全部希望；（3）它导致
19、了重新评价某些被普遍认可的数学哲学；（4）它把一个新的、强有力的、内容丰富的、已经提出并开创了许多新的研究途径的分析技术，引进到了基础研究中。本讲稿第三十五页，共三十八页第一不完全定理第一不完全定理对任一形式算术系统，如果它是相容的，则一定存在这样的公式，该公式及其否定在系统中都不是可证的。对于任一形式数学理论，如果它是相容的，并且它是足够复杂的，则该理论中必定存在既不可证明也不可否证的公式。从语义上说，即任一足够复杂的形式理论，其定理不可能穷尽该理论之领域的所有真理。本讲稿第三十六页，共三十八页哥德尔第二不完全定理，哥德尔第二不完全定理，可以表述为：“如果形式系统PA是相容的，则这种相容性在PA是不可能证明的。”该结果同样可以扩展为：如果一个足够丰富（含形式算术）的形式数学理论是相容的，则其相容性不能在系统之内得以证明。特别是，类型论和ZF等功利化集合论系统，都不可能在本系统内证明自己的相容性。本讲稿第三十七页，共三十八页可以说，哥德尔不完全定理否定从形式技术上彻底解决悖论问题的可能性，而在简单类型论和ZF等公理化系统中又为发现新的悖论，所以目前关于罗素悖论的讨论技术上基本被解决，探讨主要着眼于哲学层次。本讲稿第三十八页，共三十八页