集合论语形悖论

集合论语形悖论第1页，共38页，2023年，2月20日，星期四一、罗素悖论1901年6月，罗素在利用康托儿的集合论解决问题时，发现了罗素悖论，在1902年罗素写信把这个反先告诉了弗雷格，使得弗雷格大为震惊，在《算术基本法则》中，弗雷格尝试用集合概念来定义数，并认为这一任务已大致完成。然而在这个时候，他得知了所谓的“罗素悖论”，这一悖论对弗雷格的事业是一个毁灭性的打击。第2页，共38页，2023年，2月20日，星期四弗雷格在他的《算术基本法则》第二卷的结尾处写了这样的一段话：“一个科学家工作完成之日，也是这一建筑物的几处倒塌之时，没有什么比这个更糟糕了。当本书即将付梓之时，罗素先生的一封信把我置于这样的境地。”“在工作已经结束时，自己建造的大厦的一块主要基石却动摇了，对一个科学家来说，没有比这更让人沮丧了”。弗雷格以一个学者对于理论和研究的深刻忠诚，承认了这一切，1902年，弗雷格在《算术基础》第二卷“后记”中将该悖论随书出版公布。第3页，共38页，2023年，2月20日，星期四什么是罗素悖论呢？这就是罗素发现的在近代由康托儿提出的集合论中间包含着的一个悖论。在素朴集合论中，集合本身也能够成为集合的元素和对象，但是集合本身能否成为自己身的元素和对象呢？有些集合本身还可以成为自己集合的一个对象，例如，元素个数不为3的集合，记作﹛元素个数不为3﹜，第4页，共38页，2023年，2月20日，星期四元素个数不为3的集合有很多，肯定不是只有3个，所以这个集合﹛﹛元素个数不为3﹜﹜，即元素个数不为3的所有的集合本身构成的集合，它的元素个数肯定不是3，那么它也应该属于﹛元素个数不为3﹜的集合。这样的集合我们称之为是属于自身的集合，记作﹛属于自身的集合﹜，即所有那些和上例相同的，能够属于自己的集合放在一起构成的大的集合。第5页，共38页，2023年，2月20日，星期四当然与这个相对还有另一种情况：即集合是不属于自身，例如﹛人﹜这个集合，集合里的元素就是世界上个人，而由人构成的集合本身只是一个集合，肯定不是人，所以它就不能属于自己。而由这样的集合—不属于自身的集合，放在一起构成一个集合，这个集合就是不属于自身的集合的集合，记作﹛不属于自身的集合﹜。第6页，共38页，2023年，2月20日，星期四我们就把所有的集合分为了两种情况：属于自身的和不属自身的，而两种不同性质的集合又分别构成了两个大的集合，即﹛属于自身的集合﹜；﹛不属于自身的集合﹜。这样两个集合我们分别用逻辑符号表示为：﹛x属于x﹜；﹛x不属于x﹜对于这两个新的集合：﹛属于自身的集合﹜和﹛不属于自身的集合﹜他们本身又是否属于自身呢？﹛属于自身的集合﹜，很明显它是属于自身的，第7页，共38页，2023年，2月20日，星期四因为﹛属于自身的集合﹜，它本身就是一个属于自身的集合，当然按照对集合的两种归类，它应该被归到属于自身那一类，所以它是属于自身的，即﹛属于自身的集合﹜属于﹛属于自身的集合﹜，即它是属于自身的，逻辑符号可以记作：﹛x属于x﹜属于﹛x属于x﹜；但是对于集合﹛不属于自身的集合﹜，如何判断它呢？就是说这个集合是属于自身还是不属于自身，这就是罗素悖论的来源。第8页，共38页，2023年，2月20日，星期四弗雷格表述如下：“为简短起见，我们称之为类K。现在让我们问，这个类K是不是属于自身。如果一个东西属于一个类，那么它就归属于以这个类为其外延的概念。这样，如果类K属于自身，那么它就是一个不属于自身的类。因此我们的第一个假定导致自相矛盾。第二，让我们假定类K不属于自身，这样它就属于以自身为其外延的概念，因此就属于自身。这里我们又一次得到同样的矛盾。”第9页，共38页，2023年，2月20日，星期四这里解释两点：第一，“以这个类为其外延的概念”，这里“一个概念是一个其值总是一个真值的函数”，即命题函项。例如人这个概念指的是X是人这个函数，某物归属于这个概念，即它可以满足X是人这个函数式（使之为真）。第二，集合的内涵和外延。第10页，共38页，2023年，2月20日，星期四第一步，我们假设它是属于自身的；假设这个集合是属于自身的，即它是集合﹛不属于自身的集合﹜的一个元素，而集合﹛不属于自身的集合﹜的元素具有什么特点呢？即不属于自身，既然我们假定它是属于这个集合的，是这个集合的一个元素，当然它也应该具有这个性质：不属于自身，这样我们经过推倒得到的结论就是：它不属于自身。而这个结果就和假设相矛盾了；第一步的假设不成立。第11页，共38页，2023年，2月20日，星期四第二步，我们假定它不属于自身；假设这个集合不属于自身，不就意味着集合﹛不属于自身的集合﹜不属于﹛不属于自身的集合﹜，由于这个集合不属于自身，按照对于集合的两个划分，要么属于自身，要么不属于自身，而它不属于自身，因此就应该被归到不属于自身那一类，即属于集合﹛不属于自身的集合﹜，由于它属于集合﹛不属于自身的集合﹜，即集合﹛不属于自身的集合﹜属于﹛不属于自身的集合﹜，而这样它不就又属于自身了，而这与我们的假定正好矛盾。第二步假设也不成立。第12页，共38页，2023年，2月20日，星期四通过两个假定，我们都得出了矛盾，两个假定都出了问题，就是说对于集合﹛不属于自身的集合﹜，我们既不能说它属于自身，也不能说它不属于自身，这不就等于说它本身无法处理了。如果我们把集合﹛不属于自身的集合﹜记作A，则我们不就得到这样的结果：假定A是A，则A不是A，假定A不是A，则A是A，因而这就是一个悖论。如果用逻辑符号表达，设﹛x不属于x﹜记作A，如果A属于A，把Ａ带入集合，得到Ａ不属于Ａ；如果Ａ不属于Ａ，根据集合定义，Ａ不属于Ａ属于集合﹛x不属于x﹜，则Ａ属于Ａ，于是悖论。第13页，共38页，2023年，2月20日，星期四理发师悖论；在一个小村庄，一个理发师挂出一块招牌，写到：“我给且仅给不给自己理发的人理发！”那么，他是否应该给自己理发呢？如果理呢，则他明显给自己理发了，按照规定他不能给自己理发；不过不理呢，它属于那些不给自己理发的人，他应该给自己理发；怎么办？通俗版本第14页，共38页，2023年，2月20日，星期四我跟且跟不与自己聊天的人聊天！第15页，共38页，2023年，2月20日，星期四二、最大序数悖论1895年，康托尔发现了最大序数悖论，1897年公开发表。最大序数悖论构建过程中使用的概念比较多，人们总认为其推导过程中一定存在着尚未被发现的漏洞，因而没引起什么危机感。罗素悖论的力量则在于它的极端简洁性。第16页，共38页，2023年，2月20日，星期四如果一个集合的任何两个元素之间，都按确定的次序关系排列，则称该集合为序集。其中次序关系为不自返、不对称而传递关系。如果一个序集的任一非空子集，都有一个在给定次序下的最初元素，则称此集合为良序集。例如集合S={1,2,3，…}是良序集，S1={…-3,-2,-1,0,1,2,3,…}是序集但非良序集。明显，任一有限集都是良序集。第17页，共38页，2023年，2月20日，星期四如果两个序集的全部元素都能一一对应，而且相应元素的次序关系相同，则称这两个集合相似。任意两个或多个集合之间具有相似关系，则称它们具有相同的序型。序数就是指良序集的序型。现在看下从小到大的自然数集{0,1,2,3，…，n，…}。显然，0之后的每一个数都是它前面的数构成的数集的序数，而0代表空集的序数。换言之，自然数集代表了所有有限序数。由所有有限序数可构成一良序的无限集合。第18页，共38页，2023年，2月20日，星期四在无限集合中，康托把由小到大的自然数集合作为最简单无限良序集，把它记做w，w称为第一个超限序数。w之后紧接着的第一个序数记为w+1，它是良序集{0,1,2,…，n,…,0}的序型。之后可得w+2，w+3,…，再之后是2w，2w+1，…，由此继续推进，康托尔把所有序数的集合本身构成一个良序集，其中每个序数都是描述在它之前的序集的序型。第19页，共38页，2023年，2月20日，星期四现在设定一个所有序数的集合O，明显所有的序数集合也是一个良序集，它也应该有一个序数Ω，那么Ω是不是O的元素？既然Ω是一个序数，那就应当作为所有序数的集合O的元素；但由于Ω是O本身的序数，根据序数理论，每一个良序集的序数都应该大于该集合的所有元素，它有应当大于O的任一元素，因而又不应是O的元素。于是，上述超序数理论导致了矛盾。第20页，共38页，2023年，2月20日，星期四康托尔反复探讨未能解决这个问题，于是写信请求希尔伯特共同探讨。他们都认为经过某个枝节的修正就能解决问题。三、布拉里-弗蒂悖论后来意大利学者布拉里-弗蒂在1897年独立发现这一问题，并将之公开发表，以下是罗素对布拉里-弗蒂的转述，内容如下：“可以证明，每个良序集的序列都有一个序数，达到并包含任意给定序数的序列比给定的序数要多出一个，并且所有序数的序列式良序的。第21页，共38页，2023年，2月20日，星期四由此可以得出：所有序数的序列有一个序数，比如说Ω。但是这种情形下，所有Ω的序数的序列有序数Ω+1，而这必定大于Ω，因而Ω不是所有序数的序数。”当时学界对待这个悖论与康托尔悖论的态度是一致的。但通过类似于罗素悖论的推导过程很容易得到矛盾等价式：Ω是O的元素，当且仅当，Ω不是O的元素。相对于前述素朴集合论，此处得到的是严格意义的逻辑悖论，史称“布拉里-弗蒂悖论”第22页，共38页，2023年，2月20日，星期四四、格瑞林悖论1908年纳尔逊和他的学生格瑞林把下面的悖论发表出来。

如果一个形容词所表示的性质适用于这个形容词本身，比如“黑的”这两字的确是黑的，那么这个形容词称为自适用的。反之，一个形容词如果不具有自适用的性质，就叫做非自适用的。例如“英语的”三字本身是汉语写成的，就不是自适用的。第23页，共38页，2023年，2月20日，星期四现在我们来考虑非自适用的这个形容词，它是自适用的还是非自适用的呢?如果“非自适用的”是非自适用的，那么它就是自适用的；如果“非自适用的"是自适用的，那么按照这词的意思，它是非自适用的，这就导出矛盾。第24页，共38页，2023年，2月20日，星期四五、悖论的影响十九世纪末及二十世纪初，数学空前兴旺发达，十九进纪七十年代康托创立的集合论是现代数学的基础，素朴集合论已被证明可以作为算数乃至整个数学大厦的基础。罗素悖论的出现直接导致了基石的动摇，产生了第三次数学危机。第25页，共38页，2023年，2月20日，星期四六、悖论的解决（一）、类型论简单类型论限制“属于”符号的应用，对每一个集合规定其类型，当且仅当“属于”号后面的类型比前面的类型大于1时，“属于”的运用才有意义。第26页，共38页，2023年，2月20日，星期四分支类型论处理谓词对任一性质按照它处理的对象进行分类；个体属于0级谓词；谓词处理的对象是个体称为1级谓词；谓词处理的对象是1级谓词或者个体，且至少有一个1级谓词称为2级谓词；…第27页，共38页，2023年，2月20日，星期四谓词处理的对象都是n级以下谓词，且至少有一个n级谓词称为n+1级谓词。规定每一等级谓词不能处理该谓词的对象总体以及更高等级的谓词，每一谓词的应用只有在低于其等级的谓词对象时才有意义；凡是涉及一个谓词对象整体的对象不能属于该整体。罗素悖论探讨对象全体是否属于本身，这种探讨不合规定；第28页，共38页，2023年，2月20日，星期四（二）、公理化集合论1908年，策墨罗提出了第一个构造公理化集合论系统解决集合论悖论的完整方案。策墨罗把矛头指向“任一特征属性可决定一集合”这个概括原则，他认为集合并不是任意特征属性都可决定的汇合，而是必须满足某些存在条件的对象。集合的存在性经由几条他精心研究而提出的几项公理加以保证：第29页，共38页，2023年，2月20日，星期四（1）确定性公理：每一集合都由它的元素唯一决定。（2）基本集合存在公理：空集存在，单元素集合存在，对偶集存在。（3）分出公理：如果谓词P对已知集合B中的所有元素都由意义，则可以从B中分出一个子集A，而A由B中所有满足谓词P的元素组成。（4）幂集公理：每一集合存在一幂集。（5）并集公理：任一集合的所有元素的元素组成一集合。第30页，共38页，2023年，2月20日，星期四（6）无限公理：至少存在一集合，空集是它的元素，且如果x是它的元素，{x}也是它的元素。（7）选择公理：若A是由不相交的非空集合组成的集合，则存在一集合，它和A的每一个元素恰有一共同元素。弗兰克尔增加了公理（8）替换公理：若f是一个函数，对一个已知集合中的任一元素x而言，f（x）也是一个集合，那么，所有这些f（x）就构成一个新的集合。第31页，共38页，2023年，2月20日，星期四1925年，冯诺依曼提出了（9）增加公理：对任一没空集合，一定有这样的元素存在，它与原来的集合没有公共元素。于是，以一阶逻辑和唯一的谓词符号属于，通过公理（1）~（9）为基础构建的公理化集合论，既可以起到康托尔作为数学基础的作用，又消除了集合论悖论，新的悖论也没有产生。一般人们把除了选择公理之外的其它公理被称为ZF系统，把包含选择公理的系统成为ZFC系统；而康托尔的集合论被称为素朴集合论。

第32页，共38页，2023年，2月20日，星期四康托尔悖论直接来自于素朴集合论中如下两个论断的矛盾：（1）存在大全集，即存在以一切集合为自己的元素的集合；（2）任何集合都有幂集，即一切集合都可扩充到一个以它为元素的更大的集合。ZF系统放弃了（1）解决悖论。第33页，共38页，2023年，2月20日，星期四七、哥德尔不完全定理哥德尔不完全定理是20世纪前30年集合论-语形悖论研究热潮的终结，也是这次研究热潮所取得的最大成就。哥德尔也因此被誉为继亚里士多德之后最伟大的逻辑学家。数学史家伊夫斯曾把哥德尔不完全定