科学网 › 标签 › 反对角线

标签: 反对角线

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

反对角线：从理发师悖论到计算机的极限: 热度 3 mayaoji 2018-2-2 16:27; 反对角线：从理发师悖论到计算机的极限马耀基 1 、理发师悖论先看两个著名的悖论。理发师悖论村子里有两类人，第一类人自己给自己刮胡子，第二类人不给自己刮胡子。村里的理发师给自己立了一条规定：他给并且只给第二类人刮胡子。按这条规定，理发师该不该给自己刮胡子呢？如果他给自己刮胡子，他属于第一类人，按规定他不应该给自己刮胡子。如果他不给自己刮胡子，那他属于第二类人，所以他又应该给自己刮胡子。因此，他给自己刮胡子当且仅当他不给自己刮胡子。还有个类似的悖论叫书目悖论。书目悖论有一些书，它的内容里出现自己的名字，而另一些书则不出现自己的名字。现在有一本书，它的内容就是收录书的名字。它只包括第二类书的名字，即那些不出现自己名字的书。这本书要不要把自己收录进去呢？如果它把自己收录进去，按规定它属于第一类书，所以它不应该自己收录进去。而它不把自己收录进去，又可推出它应该把自己收录进去。 2 、反对角线方法这两个悖论本质上是相同的，下面以书目悖论为例，分析这两个悖论产生的原因。假设一共有四本书，分别是金庸的《碧血剑》《连城诀》《鹿鼎记》《侠客行》。根据它们的内容是否出现书的名字，绘制了下面这个表格。表格里 √ 表示行里的书出现了相应列的书的名字， X 则表示不出现名字。比如第二行第一列是《碧血剑》，其他几列分别是 √ 、 X 、 √ 、 √ ，表示《碧血剑》这本书里出现了《碧血剑》《连城诀》这两个书名，而《鹿鼎记》《侠客行》这两个名字则没出现。我们把收录书名的这本书叫《目录书》，因为《碧血剑》这本书出现了自己的名字，所以《目录书》不收录它，《连城诀》没出现自己的名字，所以目录书收录它，由此类推。《目录书》那一行的符号，实际上是将相应列的对角线上的符号取反，比如对角线上《碧血剑》那一列的符号是 √ ，则《目录书》在相应列上的符号为 X ，对角线上《连城诀》那一列的符号是 X ，所以《目录书》在相应列上的符号为 √ 。可见，目录书必然不同于那四本书里的任何一本，因为它和任何一本最少有一个地方不同。因为《目录书》也是一本书，所以把它添加到表格的列中。问题是：下表右下角那个方格，应该是 √ 还是 X 。它是将对角线上的记号取反，现在对角线上的记号就是它自己。自己和自己相反，这是矛盾的。理发师悖论和书目悖论的根源是这样的：给定一个集合，我们用反对角线方法构造出一个和原集合所有元素都不同的新元素（简称反例），当这个反例又属于原来的集合时，就出现了悖论。举个假想的例子，我们要画一棵树，使得它和世界上所有的树都不一样。我们把全部的树编号，然后这样设计这棵新树：它在高度上跟 1 号树不同，叶子数量跟 2 号不同，树枝长短跟 3 号不同，……，总之它和每一棵树都最少有一个地方不同。显然，这将是一棵与众不同的树。但画完后我们发现它竟然和某棵树一模一样，咄咄怪事！悖论！ 3 、罗素悖论及其他利用反对角线方法，我们可以构造出很多悖论。最有意思的还是数学悖论，因为数学出现悖论事关重大，可能会动摇科学的大厦。最有名的数学悖论可能是英国哲学家罗素发现的悖论了，它实际上也是用反对角线方法构造出来的。罗素悖论集合有两种：自属集和非自属集。自属集是指集合本身是自己的一个元素，而非自属集则相反，自己不能作为自己的元素。比如 {1} 就是非自属集，因为 {1} 不是 {1} 的元素。而非石头集就是自属集，因为非石头集是所有不是石头的东西所组成的集合，而非石头集本身也不是石头，所以它也是非石头集的元素。所有的非自属集放在一起组成一个集合（简称集合 A ），请问集合 A 是自己的元素吗，容易推出如果 A 属于自己则 A 不属于自己，如果 A 不属于自己则 A 属于自己。如果用数学语言叙述罗素悖论，则两行就够了。理查德悖论理查德悖论和前几个悖论有点不同，前几个悖论如果用表格表示，它第一行和第一列的元素是相同的，比如书目悖论中第一行和第一列都是书名。而理查德悖论不是这样，它要用到编码方法才能构造反例，这个方法在后面会用到。理查德是一位中学教师，他发现了下面的悖论。自然数的某些性质可以用有限长的语句描述，比如“能被 2 整除”，“大于 5 ”等。现在给每个性质分配一个号码，这个号码也是自然数。有的性质的编号数本身不具有它所编号的性质，这种数称为理查德数。举个例子，假设“能被 2 整除”这个性质被编为 7 号，那 7 就是理查德数，因为它不能被 2 整除。有的性质的编号数本身具有它所编号的性质，这种称为非理查德数。假如“大于 5 ”这个性质被编码为 10 ，则 10 就是非理查德数。可见，理查德数和非理查德数，也可用有限长的语句描述，它们本身也应该有编号。假设“是理查德数”这个性质的编号为 n ，现在问 n 是不是理查德数？容易得到：如果 n 是理查德数，则它不是理查德数。如果 n 不是理查德数，则它是理查德数。贝里悖论一位叫贝里的图书管理员也提出了一个悖论，罗素称这是理查德悖论天才般的简化。它是这样的：考虑“不能用少于 100 个汉字描述的最小正整数”这句话。假设这句话描述了一个数，则这个数是不能用少于 100 个汉字描述的，但这句话本身少于 100 个字，矛盾。所以它没有描述这个数。假设这句话没有描述一个数，这又与事实不符，因为它确实描述了一个数。 4 、反对角线方法的应用我们在最后一部分再讨论如何解决这些悖论，这部分先讨论反对角线法在无穷集合上的应用。无穷集合理论是德国数学家康托创建的，也是他先把反对角线方法用到这个理论上。无穷集合有很多有趣的性质，数学家希尔伯特曾用无穷旅馆的例子来说明它们：设想一家旅馆，里面有无限个房间，所有的房间都客满了。这时来了一位新客。按照日常的经验，旅馆客满就安排不下新的客人了，但无穷旅馆不一样。旅馆主人把 1 号房间的旅客移到 2 号房间， 2 号房间的旅客移到 3 号房间， 3 号房间的旅客移到 4 号房间等等，这样继续移下去。就这样无中生有般空出了 1 号房间，新客人就被安排住进了这个空房间。把客人安排进旅馆，本质上是给每人分配一个不同的自然数。所有的客人组成了一个无穷集合，加进来一个客人还是无穷集合。这两个无穷集合每个元素都能分配一个不同号码，即这两个集合的元素都能和自然数形成一一对应，用数学的话来说这两个无穷集合都是可数的。那是不是任意一个无穷集合都是可数的呢？下面来讨论这个问题。定理 1 ：可以给每个整数都分配一个不同的自然数号码，即整数是可数的看起来不可能做到，因为整数有正有负，按照定义自然数就是正整数，它只是整数的一部分。但细想这件事不难，把所有的整数按下列顺序排序： 0 ， 1 ，— 1 ， 2 ，— 2 ， 3 ，— 3 ，…… 排第一位的分配号码 1 ，第二位的分配 2 ，第三位的分配 3 ，……，这样问题就解决了。用专业的话，整数集和自然数集的元素能形成一一映射。整数虽然包含了自然数，但严格来说两者是一样多的，因为按照数学定义，两个集合的元素一样多，就是指两者的元素能建立一一对应。定理 2 ：不可能给每个自然数集合分配一个不同的自然数号码假设可以做到，那么我们用 S 1 、 S 2 、 S 3 ……来表示这些集合。把它们按顺序排列，用下面的表格来表示它们的元素，其中 √ 表示相应列的数字是相应行那个集合的元素， X 则相反。比如 S 1 包括 1 和 3 ，不包括 2 和 4 。我们可用反对角线方法构造出一个新的集合，这个集合和表格里所有的集合都不相同。而按照假设，所有的自然数集合都在表格里了，矛盾。所以假设错误，我们无法给每个自然数集合都分配不同的号码。上面的证明可以推广：任一集合都无法和它的幂集的元素形成一一映射。定理 3 ：不可能给每个实数分配一个不同的自然数号码只要证明无法给 [0,1) 之间的实数分配不同的号码就行了。假设可以做到，那将它们排列如下： a 0 、 a 1 、 a 2 、 a 3 、 a 4 、 a 5 ……。每个小数都可以用无穷小数表示，比如 0.1=0.100000 ……，后面全是 0 。所以序列中的每个数可以展开如下（下面的每一个 a mn 都是 0 到 9 中的一个数）：用反对角线方法构造新的小数 D ， D 的每一位小数都和对角线上的元素不同，这样得到的 D 不同于序列中的任一个小数。而 D 又在 [0,1) 之间，矛盾。所以不能给 [0,1) 的实数分配不同的号码，所以不可能给每个实数分配不同的号码。（注释 1 ）想一想，实数可以按自然数顺序排序的假设在证明中起到了什么作用？能不能把证明定理 3 的方法用于证明有理数不可能分配不同的号码，即定理 2 不成立，为什么？定理 4 ：存在无法用计算机计算的函数首先说明，可计算、可用计算机计算、可用程序计算这些概念在这里是同一个意思。（注释 2 ）另外，为了简单，我们这里考虑的函数，变量都是自然数。我们知道计算机能做很多运算，比如能进行加法运算。进行加法运算实际上是计算 z=x+y 这个函数。一个计算 z=x+y 的程序，就是输入 x 和 y 的值，输出 z 的值，即如果输入 2 和 3 ，它就输出 5 ，输入 3 和 4 ，它就输出 7 。函数 z=x+y 是二元函数，其中 x 、 y 是自变量， z 是因变量。又比如，函数 y=x 2 也是可以计算的，这个函数是一元函数， x 是自变量， y 是因变量。无法计算的函数，是指不存在这样的程序：当输入自变量的值时，程序总是输出这个函数的因变量的值。我们给所有的计算机程序分配自然数号码（或叫编码），就像每个人都有不同的身份证号码一样，每个程序也有不同的号码。这里编码的不单是指现在世界上存在的所有程序，而是指理论上所有可能的程序，这样的程序数量显然是无限的。（注释 3 ）程序能够编码，这是需要严格的证明的。这里省略证明，我们直接接受这个结论。因为所有的程序都是可以编码的，所以所有计算一元函数的程序也可以编码。现在将所有计算一元函数的程序编号，将这些它们记为 P 1 ， P 2 ， P 3 ，…… P n ，……，每个程序对应着一个可计算函数。这些程序对应了所有可计算的一元函数，因为按前面的定义，能计算的函数就是能用程序计算的，而所有计算一元函数的程序都在这里了，所以可计算的一元函数也全在这里。现在反对角线法构造函数 d ： d(n)=2 ，如果 P n (n)=1 ， d(n)=1 ，如果 P n (n) ≠ 1 ，或者 P n (n) 无定义。（ P n (n)=1 ，表示当输入为 n 时，程序 P n 的输出是 1 。）函数 d 与任何一个程序所计算的函数都不同，所以它是任何一个程序不能计算的。容易证明，如果 d 是可计算的将导致矛盾。假设它是可计算的，则计算它的程序必然分配有号码，假设是 s ，则函数 d 就是程序 P s 计算的函数， P s (s) 的值是什么？按照定义，如果 P s (s)=1 ， d(s) ≠ 1 ，但程序 d 就是程序 P s ，所以矛盾。同样，如果 P s (s) ≠ 1 ，也有矛盾。这里能够构造出无法计算的函数 d ，本质原因是函数的数量比程序多。 5 、进一步的讨论反对角线方法，是从一个给定集合构造新元素（即反例）的方法。当这个反例又属于原来的集合时，就出现了悖论。那怎么解决悖论呢？有人认为反例实际上不存在，比如在理发师悖论和书目悖论中，符合规则的理发师和目录书不存在。但这个方法不能用于罗素悖论，因为对任意一个性质，所有符合这个性质的元素就组成一个集合，这叫概括原则。解决罗素悖论有两种主要思路。第一种思路是不允许数学命题出现自指，从而无法构造反例。罗素自己采用了这种思路，他认为自指会出现恶性循环，所以禁止自指，在此基础上他建立了类型论。另一种思路是将反例排除在原集合之外。比如有的人不承认概括原则，认为把所有非自属集放在一起不是一个集合，所以构造出来的反例不是原来集合中的元素，因此不构成悖论。按这种思路，数学家策墨罗重新规定了成为集合的一些条件，建立了公理集合论，这理论里不会出现罗素悖论。使用反对角线法构造悖论关键在两点： 1 、能够构造反例， 2 、反例属于原集合的一员。要构造反例，必须先知道对角线上的值，所以必须要知道表格中第一行的元素和第一列的元素。如果第一行和第一列不仅元素相同而且排列顺序相同，我们一定能构造出反例。理发师悖论、书目悖论、罗素悖论都是这样，比如书目悖论中，第一行和第一列都是那些书名且顺序相同。如果第一行和第一列的元素不同，第一行的元素是自然数，比如理查德悖论，这时第一列的元素必须能够按自然数顺序排列（即可数的），才能构造反例。比如构造不可计算的函数 d 时，要用到对角线 P n (n) 的函数值，这需要先给程序编号才知道 P n 是什么，不知道 P n 就无法构造反例。在上文证明定理 2 、 3 、 4 时，先假设第一列的元素是可数的，然后构造反例出现矛盾，从而推出假设是错的。这里假定了数学不会出现矛盾。实际上在建立公理集合论后，人们还没有在数学上发现矛盾。有时候虽然能构造反例，但反例不属于原集合的一员，就不会出现矛盾。比如将所有有理数排列，然后用反对角线法构造一个反例，但由于我们不能保证这个反例就是有理数，因此不能用反对角线法证明有理数不可数。注释： 1 、这里的证明是不严格的。因为同一个小数有不同的表示方法，比如 0.100000 …… =0.099999 ……。用反对角线方法构造出来的 D ，看上去虽然和序列中的任一个小数不同，但不能保证它们就不是相同的小数。不过对上面的证明稍作修改，就可以弥补这个漏洞。 2 、这篇文章说的计算机是指图灵机，我们现在所用的计算机本质上都是图灵机。按照丘奇图灵命题，可计算函数和图灵机可算的函数这两个概念是等价的。 3 、不同的程序，功能可以是相同的。比如程序 A ，对输入的变量先加 1 ，再加 2 ，然后将结果输出。程序 B 则是先加 2 ，再加 1 。程序 A 和 B 是不同的，所以它们分配到的号码是不同的，但是功能相同。相关文章说谎者悖论：从鳄鱼难题到数学证明的极限; 个人分类: 逻辑学|11570 次阅读|6 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 反对角线

相关帖子

相关日志

关闭安全验证