【转】不同寻常的数

(转载者)【逻辑引擎】简序:虽然关于超限数的一些理论(特别是大基数)遭到某些直觉主义者或构造主义者的诟病,但对我个人而言,如果非要让我在我所有的知识中挑选出唯一一种美到令我窒息的东西,那就是超限数。这是疯子数学天才康托尔(Georg Cantor)开启的通往无穷地狱的神奇窗口。对我而言,超限数比任何疯狂的幻想小说都更加疯狂。你一旦进入了这个浩瀚的世界,就会发现自己所知道的一切,甚至是自己最为疯狂的幻想,都是无限微不足道的。相比于原则上不受任何限制可随意创造甚至连逻辑含混不清自相矛盾都可容忍的幻想小说设定,超限数却是在绝对严格地遵守最苛刻规则的同时,又绝对无限地突破任意强大的智力能够触及的极限。即便是强大到能创造整个宇宙的造物主,拥有对人类而言真正无穷大的计算能力,在超限数的层级上充其量可以比我们多走一点点。而在超限数这个浩瀚的世界中,多走这一点点只不过是无限微不足道的进展。仅凭这一点,我就愿意用一生去欣赏它。

虽然本文是一篇很不错的科普,但真的想要通过本文体会到超限数的美妙之处,还是需要读者对此多少有所了解,否则可能会对超限数这种奇异的数学结构感到莫名其妙。

如果读者居然能硬着头皮把文章看完,哪怕最终像文中阿基里斯一样不省人事,你也已经欣赏到了超限数的华丽皮毛。如果你居然像文中的乌龟女士一样对此乐此不疲,愿意花更多精力去了解和研究,说明你跟我一样,病的不轻药不能停,你一定会对我前面所说的话产生强烈的共鸣。

在此,“超限”感谢若干年前将法文原著翻译成中文的·异调·,这篇文章连英文版我都没找到过,没有·异调·的贡献,中文读者不知道何时才能接触到这篇如此华丽的数学基础科普故事。虽然我在看到这篇文章之前就已经对超限数的美丽感到窒息,但这篇文章让我从窒息跌入了窒息的窒息次方、窒息的窒息的窒息次方次方……的无底深渊 ;-)

最后,一切荣耀归于原作者David Madore…………Mad-ore?疯子矿?!!Cantor是个疯子,这位居然是疯子矿,难道超限数的震撼真的只有真正的疯子才能领略么?好吧,能欣赏到如此绝美的东西,我也宁愿当个疯子。

——原来在BBS上发表的译文不支持TeX公式,许多符号只好用字符替代,我此次转载将这些符号全部替换成了TeX公式。此外,我对一些引起某些读者困惑的内容加了几条新的注释。

本文链接 http://zhblog.engic.org/20141003-015609/
————————————————

不同寻常的数[注1]
原作者 David Madore
中译者 异调(原三思科学BBS网友:冷饭,留法数学博士)
法语原版

阿基里斯和乌龟正在参观一个现代艺术展览,他们欣赏着一幅除了八根水平黑色横线外一片空白的画,画的题目叫“序数8”。


序数8

阿基里斯:对你说吧,我挺喜欢绘画的。不过这,这也太过分了,这个阿列封斯·阿莱[注2]……

乌龟(好笑地):阿列封斯·埃夫伊!绰号“阿列夫伊”。阿列封斯·阿莱是个作家,不是画家。

阿基里斯(不理睬乌龟):……那幅一片空白的画,取名叫“序数0”,大概可以算是好创意。画张一根线的画,叫作“序数1”,也还过得去。接下去的“序数2”,也马马虎虎。可一直画到这里,我觉得真太夸张了。(阿基里斯不安地往右边望望,又忙恐惧地转过头来。)我说他以这为主题创作的作品可真不少哪。

乌龟:你要求太高了,阿基。这是他青年时期的作品。要是你乐意,我们往前面走走:他在往后的生涯中画了更有意思的作品。

(乌龟开始以一个令阿基里斯吃惊的速度朝前走——他几乎跟不上她的脚步。)

阿基里斯:我说,他这青年时期的作品有那么多啊,能让你走得这么快。

乌龟:当然喽。事实上有无限幅。

阿基里斯:无限幅?那我们就永远走不到头啦!

乌龟(非常好笑):我还以为听见芝诺在说话呢。你知道的,就是那个以为你永远赶不上我的哲学家。讲的自然都是些蠢话。(她走得越来越快。)在有限长的时间里做无限件事情并非不可能,在有限的空间里放上无限件东西也并非不可能。只有希腊人才会怕无限怕成这个样子。

阿基里斯(狠狠地瞪乌龟一眼):我才不怕无限呢!我只是担心这么走下去有点单调……尤其是快要走完的时候。

乌龟:别担心,有多种多样的无限。嗨!我们到了。

(阿基里斯吃惊地四下张望。他有点不太明白自己是怎么走到这里来的。在他的前面是一幅新的画,题目为“序数\omega”。画的还是水平横线。不过这次这些线越往上就排得越紧,在画的顶部,线条排得密密麻麻分不清了。)


序数\omega

阿基里斯:噢,这个就好多了。横线渐渐接近,就好像是排向一条地平线。我想它们大概有无限条吧……

乌龟:当然喽,事实上正有无限条。

阿基里斯:我记得刚听你说过这玩意,这画大概就是那个“序数”系列作品的最后一幅吧。这个\omega表示画家希望终结此主题,然后去画点别的东西的愿望[注3],这也就是那些终结于地平线的横线所象征的。我不禁想起了歌德《浮士德》中最后的诗句:“Das Unzulangliche / Hier wird’s Ereignis.”[注4]

乌龟(嘻嘻哈哈):你可真了不起啊,阿基!在你又要引用德日进[注5]语录之前,我建议你先往右边看看。

(阿基里斯听话地往右看,当他瞧见那幅题为“序数\omega+1”的画时,张口结舌。这是一幅和“序数\omega”几乎一模一样的画,差别就是在最上头多了一条线。)


序数\omega+1

阿基里斯(快崩溃了):哎呀呀呀!我早该防着这手了……要是我现在问你什么是“序数”,还不算太晚吧。

乌龟:不算晚。这并不难:一个序数,就是一架梯子。

阿基里斯:看看这些一级一级可怕的小杠杠,我早该明白这事了。就这么多?

乌龟:这是一架你可以无限地向上迈的梯子。但是有条最最基本的规矩,就是谁都不能无限地向下迈。

阿基里斯:我好像又糊涂了。

乌龟:这很简单。无论你选中梯子上的哪级横档,然后踩住它下方的某一级横档,这样就是往下迈一次,然后再这么往下迈一次,一直这样走下去……结果你总会在有限的步数里走到最底下。比方说,在我们的序数\omega里,那些横档从下到上编号为0,1,2……等等(也就是说以自然数编号):要是你想无限次地往下迈,你就得找到一个无限长的、严格递减的自然数序列,可这是不可能的,因为你最后总归会碰上0。相反地,你可以无限次地向上迈,比方说0,1,2,3……,或者1,2,4,8……号,或者其他别的什么横档的序列。要是你把这画头朝下挂反了,那就不是一个序数了,因为那时你可以无限地往下迈。

阿基里斯:这么听起来,好像还不算太复杂。

乌龟:别自以为是了!序数是通往数学天堂的梯子,懂得它们,就可以算是有点懂得了全部数学。我说过的那条规矩,看起来好像挺简单的,可正是它给予序数所有的力量。对于某些复杂得可怕的序数来说,意识到不能无限地往下走这点,是可以让人震惊不已的。

阿基里斯(被吓住了却还有点嘲笑的口气):哇!数学的秘密全在一架梯子的顶上!可这些序数有什么用场呢?

乌龟:用场大得很。首先,我们可以对它们做加法:要把两个序数\alpha\beta加起来,我们只需把\beta的梯子放在\alpha的梯子上面。我们把它写成\alpha+\beta

阿基里斯(洋洋得意):\omega+1就是这么来的,我们把序数1,也就是只有一级横档的梯子,放在梯子\omega顶上。

乌龟:就是这样。“加1”,也就是在一架梯子顶上加上一级横档这种特殊情况,我们叫它为取一个序数的“后继”。

阿基里斯:于是\omega+1就是\omega的后继喽。因为要是我把\omega+1顶上的那级横档去了,就又得到\omega。同样地,\omega+2\omega+1的后继……可是,哎呀你说,\omega这东西,它是什么东西的后继啊?是\omega-1的后继?

乌龟:不是的。没有\omega-1这种东西。\omega不是任何序数的后继,因为你不能去掉它的最上面那一级横档:那根本就不存在。在每级横档的上面,都还有另一级,所以没有最上面的那级。那些和\omega一样的,不是其它哪个序数的后继的序数,我们把它们叫做“划限序数”,其他的序数我们则称为“后继序数”。要注意这和有限无限没关系,\omega+1是无限的,但是它是后继序数,因为它有最顶上的那级横档;而0呢,它是没横档的梯子,是有限的,却是个划限序数,因为它一级横档都没有,就别提最顶上的那级了。

阿基里斯:我不能去掉最上面的那级横档,可我总能在其他随便什么地方去掉一级吧。比方说,最下面第一级。在\omega里,最下面的那级横档还是有的。

乌龟:当然啦,无论什么序数都有最下面的那级横档。要是没有的话,那么任何一级横档下总会有其他横档,这样就可以无限地往下走了,但这是不被允许的。唯一的例外,就是0。另外,一架梯子上的最下面第一级横档叫0号横档,第二级叫1号横档,等等。序数的每级横档,它们本身就是序数,它们恰好就是小于整条梯子序数的那些序数。比方说,\omega的横档,恰好就是所有自然数;而\omega+1的横档,就是所有自然数,再加上最后一级横档,也就是横档\omega\omega+2的横档,就是所有\omega+1里的横档,再加上一级名叫“\omega+1”的横档。

阿基里斯:我不知道跟没跟上你说的话。要我说,两个序数里面总有比较大的一个,这事情就已经不是那么显然了。

乌龟(不容置疑地):这不是那么显然,可这是个事实。两个序数之间总可以比较大小。任何一个序数就是一架梯子,它上面的横档恰好由比它小的那些序数来编号[【逻辑引擎】注1]。

阿基里斯(不知所措):你说了这些,还是没回答我原来的问题啊。要是我把\omega最下面那级横档去掉,我就得到了一个小一点的序数……

乌龟:不对。你得到的还是一模一样的东西。从\omega下面去掉一级横档不改变任何东西,只要把横档的编号换一下就可以了(1号横档改名为0号,2号改名为1号,如此这般)。这序数还是\omega,它没有减小。

阿基里斯:这可真难以置信!我去掉一级横档,可剩下来的还是和原来的一样多!

乌龟:不仅仅是和原来一样多,而且它们的排列方式也和原来的一样。你要是在最下面加上一杠也是一回事。

阿基里斯:可你说过\omega+1\omega不是一回事……

乌龟:这是对的。可是在最下面加一杠,那是1+\omega,而它,却和\omega是一回事。

阿基里斯:等等!你是说1+\omega=\omega,而\omega+1>\omega喽?我要是在最下面加一杠,横档还是和原来一样多;我要是在最上面加一杠,横档就变多啦!到底是你脑子有病还是我脑子有病?

乌龟:谁的脑子都没病。不过你说的不是太正确。1+\omega=\omega而且\omega+1>\omega,这是对的,但是这不等于说\omega+1上的横档要比\omega上的多。一个序数,可不是简单的一堆杠杠:这是一堆以某种形式排放的杠杠。要是你把这些杠杠搞乱了,你就丢掉了序数,剩下的只是某种叫“基数”的更含糊的东西。这种情况下,\omega\omega+1就没区别了,其实就算和\omega+1729也没区别:所有这些序数里的横档的数目是一样的,也就是基数相同,大家一般叫它\aleph_0[注6]。不过这和它们作为序数时有区别这点并不矛盾。

阿基里斯(厌倦地):好,就算你说得对吧。我建议我们继续参观作品\omega+2\omega+3和它们那一伙吧,我可以想像它们都长得很象。还有啥?就完了?

乌龟:完了?想得可真荒唐。你跟着我就是了。

(在超空间中再次小小一跃后,阿基里斯和乌龟站在了一幅题为“序数\omega 2”的画前。)


序数\omega 2

阿基里斯:哈哈!这是一个\omega叠在另一个\omega上啊!我猜这就是为什么这个序数叫\omega 2吧。它不就是\omega+\omega吗?

乌龟:对极了,华生!多敏锐的观察力啊![注7]事实正是如此,我们有\omega 2=\omega+\omega。另外,\omega 2表示我们把序数2的(两根)横档的每一根都替换成序数\omega的一个拷贝。

阿基里斯(被迷住了):嗨,我说,这么多杠杠,可真有好些啊!

乌龟:噢,其实和刚才一模一样多。你看,\omega 2的横档是这么排列的:有第一个序列,就是老的那个:0、1、2、……,然后这个,就是新的那个:先是横档\omega,然后再是\omega+1,然后\omega+2、……。现在,假如我把这些杠杠重新排列一下,我先放上0,然后\omega,然后1,然后\omega+1,然后2,然后\omega+2,这么继续下去……那么,要是以这个顺序排列的话,我就得到了一模一样的……

阿基里斯:\omega!所以说,虽然\omega 2是一个比\omega大得多的序数,可是它们上面的横档的数目却是相同的。

乌龟:正是如此。它们有相同的基数。这两个都被称为是“可数的”。另外,2\omega\omega是同一个的序数,因为2\omega就是把\omega的每根横档都换成两根,这样做其实既没增加横档的级数,也没改变它们的排列方式。

阿基里斯(大吃一惊):是啊!这后面,又有\omega 2+1,然后\omega 2+2,然后\omega 2+3等等,然后在这一堆的后面,我想就该有\omega 3了,它就是三个\omega叠在一起。然后又是\omega 3+1等等一直到\omega 4,再往后就是\omega 5\omega 6、……这个阿列夫伊的绘画,就是这些了吧?

乌龟:你说的很有道理。不过还不能停下来。

阿基里斯:啥???后面还有东西?

(乌龟(跑够了)打了个响指(乌龟做这种事,和她能跑步一样,都很让人吃惊的),她和阿基里斯正站在一幅名叫“序数\omega^2”的画前。阿基里斯心悦诚服地陷入了沉思。)


序数\omega^2

阿基里斯:我懂了!它其实先是一个\omega,然后再在上面叠一个\omega,然后再一个,一直这么叠上无穷次。

乌龟:一直这么叠上不多不少\omega次。换句话说,把\omega的每根横档都换成一整个\omega,我们就得到了\omega^2=\omega\omega。接着呢?

阿基里斯:接着就是\omega^2+1\omega^2+2,这么一直下去就到了……就到了……

乌龟:就到了\omega^2+\omega=\omega(\omega+1),就是在\omega^2的顶上叠上一个\omega,换种方法也可以是把\omega+1的每根横档都换成一整个\omega

阿基里斯:我猜它和\omega+\omega^2不一样吧?或者说和(\omega+1)\omega不一样?

乌龟:是这样的!\omega+\omega^2简化了其实就是\omega^2。说到(\omega+1)\omega,它是把\omega的每根横档都换成一整个\omega+1,可是这个“+1”会被它上面的那个\omega吃掉,于是最后我们就重新回到\omega^2上。

阿基里斯:顺便说一下,我忘了问你……我想\omega^2,这东西,它里面的横档总比\omega里的要多吧?

乌龟:还是不对。你可以把它里面的横档重新这么排列:先是第一个\omega里的0号横档;然后是第二个\omega里的0号横档,后面紧跟第一个\omega里的1号横档;然后是第三个\omega里的0号横档,后面紧跟第二个\omega里的1号横档,再接上第一个\omega里的2号横档;然后是第四个\omega里的0号,紧跟第三个\omega里的1号,再接上第二个\omega里的2号,再接上第一个\omega里的3号;然后是第五个\omega里的0号……

阿基里斯:够啦!我啥都没听懂,不过我相信你说的,这么干就又能得到\omega。还是重新爬我们的梯子吧……\omega^2+\omega的后面,就是\omega^2+\omega+1,这么下去一直到\omega^2+\omega 2,然后就是\omega^2+\omega 3,再下去我想就要碰上\omega^2 2了。

乌龟:完全正确。这是两个\omega^2叠起来的怪物。这张就是了。(她打了个响指。)


序数\omega^2 2

阿基里斯:很简单嘛。重复上面的步骤,就有\omega^2 3\omega^2 4等等。在这后头,我想就是\omega^2\omega了。

乌龟:你学得很快啊!我们到了。它叫\omega^3


序数\omega^3

阿基里斯:这画布开始有点不够用了。看上去跟条形码似的。好,我可以猜到后面都有点什么了,有\omega^4\omega^5。喏,序数不就是这样嘛。

乌龟:不对!所有这些以后,还有\omega^\omega。(她带路到画前。)


序数\omega^\omega

阿基里斯:哎哟,这图看了叫人脑瓜疼。我啥都看不清。

乌龟:为此展览的组织者特地为那些有耐心一直走到这里的人,准备了一幅示意图:在左半边,我们看到了\omega^\omega,其中的每条横档都是我们在此之前看见的那些序数。然后,在右半边,我们只画出了代表0、\omega\omega 2等等(也就是\omega在某种意义上的倍数)这些序数的横档。很有趣的是,这样构成的梯子,它本身也还是一个序数,而且仍旧是\omega^\omega,也就是说,我们把这个序数结结实实地“除以”了\omega,结果还是得到了它本身。再后面的那些列中,是相应的\omega^2的倍数,\omega^3的倍数的那些横档。而最后,最右边的那一列,是所有\omega的指数,也就是说0、1、\omega\omega^2等等。这一次,这样构成的梯子就不是\omega^\omega了,而是\omega


\omega^\omega的结构

阿基里斯:噢,是啊,我想我开始看清楚了。不过我觉得还是有必要问问你,就是这个,\omega^\omega里的杠杠数目,要比\omega里的多吧。

乌龟:还是错了。[【逻辑引擎】注2]我给你举一种依次罗列\omega^\omega中横档的方法:首先我们有数列1、2、3、……然后把所有这些数作素因子分解:1=2^02=2^13=3^14=2^25=5^16=2^1\times 3^1等等。然后我们可以推出,对\omega^\omega的任何一条横档:2的次数对应着最后的常数,3的次数对应着\omega的倍数,5的次数对应着\omega^2的倍数等等。最后,这就给定了一个次序:0、1、\omega、2、\omega^2\omega+1\omega^3、3、\omega 2\omega^2+1……等等。按照这个方法,这个序列里有\omega^\omega的所有横档,只不过次序全打乱了,可无论怎么说所有横档都在里面。

阿基里斯(精疲力尽):我投降!

乌龟:我们可以在这里看见序数还有另一个有趣的性质,也就是它的共尾性。

阿基里斯:哦,这是什么东西?

乌龟:这是兔子眼里的序数。

阿基里斯:兔子?这干它们什么事?

乌龟:它们在爬梯子的时候也是蹦蹦跳跳的。所以它们可以一蹦就跃过许多横档——事实上想跃过多少就跃过多少。就象我们现在参观这个展览时做的那样。它们试着要一直蹦到梯子最上头。兔子可以在序数的每根横档上都踩一次,如果它这么做,它就得跳恰好和这个序数一样多的次数。在\omega这种情况下,它也可以只跳在偶数号的横档上。可是无论怎么跳,它还是得跳\omega次才能跳上梯顶。因为比\omega少就意味着跳有限次,这意味着它只跳过了有限条横档,可是只跳过有限条横档是不能够爬到\omega的最上头的。但是对于\omega+1(其他后继序数也一样)来说,它可以一下就跳在最后那根横档上。所有有自尊心的兔子都会这么干的,因为兔子很懒。[注8]

阿基里斯:为了爬\omega^\omega这个梯子,懒兔子会怎么干呢?

乌龟:它会跳在1、\omega\omega^2等等那些\omega的指数上,也就是示意图右边那列表示的序数。按这个方法,它们只要按照爬一架\omega模样的梯子,就能在\omega^\omega这梯子上爱爬多高爬多高。因为这是最佳的爬法,我们就说\omega^\omega有共尾性\omega。我们前面碰到过的划界序数都有共尾性\omega(至于后继序数,我们规定它们的共尾性为1)。

阿基里斯(不再很感兴趣):我不知道兔子还懂数学。不过要是乌龟也懂数学,为什么兔子就……哎,我说,后面还有展览吧?

乌龟:当然啦。可是图画变得越来越复杂,难以看清楚。在\omega^\omega的后面,重复一遍我们前头一直到现在所做过的又长又讨厌的步骤,就可以得到\omega^\omega 2,然后再重复一次就是\omega^\omega 3,这么一直下去到\omega^\omega\omega,这也就是\omega^{\omega+1}。如果我们把产生出它的步骤重复下去,就到了\omega^{\omega+2},一直下去就得到\omega^{\omega+\omega}也就是\omega^{\omega 2}。把\omega个这样的东西叠起来就是\omega^{\omega 2+1},这么继续下去就有\omega^{\omega 3}。同样地可以得到\omega^{\omega 4},你可以这么一直重复下去。所有这些以后,就是\omega^{\omega^2}。这么继续下去,再这么继续下去,就到了\omega^{\omega^3}。这么做到底,就是\omega^{\omega^\omega}。然后,你可以叠着\omega玩:可在\omega\omega^\omega\omega^{\omega^\omega}等等这串到了底,你不能再用\omega这个符号了,这就得使用一个新符号:我们记它为\epsilon_0。一般在这个层次上的想像,会使大家开始晕头转向,有人就会以为自己是三楼楼长了[注9]。所以我们不准备去看那幅画,我害怕你会发起小小的司汤达综合症[注10]来。

阿基里斯(倒吸一口冷气):这\epsilon_0,它绝对是巨大无比啊!

乌龟:唉,兔子们总可以很快地通过踩着\omega\omega^\omega这样下去的横档跳到顶上的。所以它还是有共尾性\omega。别看它是那个模样,它仍是可数的……我们当然有\omega^{\epsilon_0}=\epsilon_0。不过我们可以考虑序列\epsilon_0{\epsilon_0}^{\epsilon_0}{\epsilon_0}^{{\epsilon_0}^{\epsilon_0}}等等的极限。这和序列\epsilon_0+1\omega^{\epsilon_0+1}\omega^{\omega^{\epsilon_0+1}}的极限是一样的。我们把它叫作\epsilon_1。同样可以定义\epsilon_2,还有\epsilon_3,然后这么一直到\epsilon_\omega。不过呢,就象你猜的那样,我们的天才画家可不只停留在这里。因为我们可以继续\epsilon_{\epsilon_0}\epsilon_{\epsilon_{\epsilon_0}}地下去,然后一直继续这个序列直到某一个序数,据我所知,还从来没有人命名过。可是它还是只有共尾性\omega,而且是可数的。

阿基里斯(精疲力竭):可是,这就永远不会完了吗?

乌龟:为什么你想让它完?为了使数学源泉枯竭,不再流淌?还有大量的可数序数……其中有一些,仅仅是由它们的存在性,就可以得出奇迹般的推论——可是我们既不能把它们写出来,也不能作计算。而所有这些,都只不过是可数序数而已,也就是说,从理论上来讲,我们都可以象我们这位天才而又疯狂的画家所做的那样,将它们画出来。可是在所有这些序数的后面,还有那些不可数的序数。最小的那个,我们叫它\omega_1,在有些古老的文献里,它叫\Omega。至于它的基数,则被记为\aleph_1,读作“阿列夫一”。这个序数从本质上来说,比我直到现在提到的那些序数都要大,包括那些有\epsilon的丑八怪。它完全是新的,因为没有兔子能够偷懒抄近路。它恰恰就是把所有阿列夫伊的画作堆积起来形成的那架梯子,也就是我们正在参观的这个展览的总长度。

阿基里斯(完全垮了):真是噩梦啊!

乌龟:是啊。我有时会看见这样一个地狱里的景象:这是一架梯子,或者说一条阶梯,看上去就如同\Omega:在顶端,有着奇妙的东西。可是我们要花上永恒的时间来攀登,我们可以爬升得和我带你看这个展览的速度一样快,可是总靠不近它的顶端。换句话说,如果你任意选择\omega_1上的横档的一个序列,它总是有上界的,也就是说总会有一级横档比你选择的所有横档都要高。就如同只用有限条横档,你不能接近\omega的顶端,只用可数无限条横档,你不能接近\omega_1的顶端。

阿基里斯(极度沮丧):这回,是最后一个序数了吧!求求你告诉我,不会再继续下去啦。

乌龟:画展嘛,就这样结束了。\omega_1是画不出来的。可这并不妨碍它存在。同它一起的,是所有横档数和它一样多的序数,那些基数为\aleph_1的序数,它们的结构要比那些可数序数(我们也称作基数为\aleph_0的序数)复杂得难以想像。也许是因为这回有了三类序数:后继序数,那些有共尾性\omega的,还有有共尾性\omega_1的。在\omega_1的后面,我们安安静静地就到了\omega_1+\omega,它的共尾性是\omega,然后重复到达\omega_1的步骤,我们就来到了\omega_1 2,它的共尾性是\omega_1,然后是\omega_1 3,这样一直到\omega_1\omega,而它的共尾性是\omega。重新沿所有的可数序数而上,我们就到达了{\omega_1}^2,它的共尾性是\omega_1,然后……

阿基里斯(嚎叫):够啦!我真受够啦!

(一个保安逼近。)

保安(对乌龟):这个坏蛋打扰您了吗,夫人?

乌龟:这不是个坏蛋,这可是个半神,马密顿之王哪。我想我大概是找到了他脚踵外另一个弱点了……[注11]我只是建议他去参观阿列封斯·埃夫尔,绰号阿列夫尔的展览。

保安:噢,是的,一提现代绘画,有些人的反应的确会是这样的。(他离开了。)

乌龟:好啦,阿基,不要这个样子嘛!你敢在特洛伊的战场上拼命,就不敢会会这个阿列夫二?再说啦,阿列夫2,这只不过是第三小的无穷基数而已。

阿基里斯(气若游丝):你在说什么?

乌龟:就是这样啊,这些我刚刚列举的序数,只是\omega_2的横档而已,它是基数大于\aleph_1的最小序数。我们把它的基数记为\aleph_2。在\aleph_2的后面有\aleph_3,这样一直下去直到\aleph_\omega。这\aleph_\omega有个很好玩的事,它是奇性的,也就是说它的共尾性要比它自己小,那就是\omega,因为虽然它大得很,但是兔子可以先跳在\omega_1上,再跳在\omega_2上这么一直跳到\omega_\omega的顶上。然后就是\aleph_{\omega+1},我们可以一直这么列下去到\aleph_{\omega_{\omega_\omega}},而且还可以一直列下去,最后就碰上了序数\alpha,它是满足\alpha=\aleph_\alpha的最小序数。它仍旧有共尾性\omega。我还要和你谈谈不可及基数,它们比我刚才讲的所有那些基数都要大得多,因为数学家甚至都证明不了它们是否真的存在[【逻辑引擎】注3]……而这些,当然都只能算是“大基数”中最小的那些。(一声巨响。可沉醉于演讲的乌龟根本没有注意到。)不可及基数和小的无限基数相比,大约就和无限基数和有限基数相比那样。然后还有超不可及基数,超超不可及基数,等等等等。可是所有这些基数和马赫洛基数[注12]比起来就只是小不点了。在一个马赫洛基数的上面,还有不可及基数,而它们的数量和所有基数的数量还是一样多。这些基数,都只是“小的大基数”,因为还有“大的大基数”,象可测基数,还有……(她突然停了下来,意识到已经根本没有人在听她说话。)阿基!(她担心极了)你昏过去了!阿基!

阿基里斯(缓缓醒来):我看见了地狱……我就在一架梯子底下……

译者注:

[注1] 原题为“Des nombres peu ordinaires”,这里ordinaire一语双关,既指“寻常”,又和“序数”(ordinal,原意为“表示顺序的”)一词相近。以阿基里斯和乌龟这两个芝诺悖论的主角的对话形式来介绍数学主题,尤其是关于无限的主题,似乎是候世达在其名著《集异壁》里的发明。在中文版《集异壁》中,乌龟是个男性的角色,因为阿基里斯总以“龟兄”来称呼,而法文版中乌龟却是女性角色,因为乌龟(La Tortue)在法文中为阴性。本文原文为法文,故译文保持乌龟的女性形象。阿基里斯又译为阿喀琉斯,是古希腊神话中马密顿国王佩琉斯和海洋女神泰提斯的儿子,半人半神的伟大英雄。

[注2] 阿列封斯·阿莱(Alphonse Allais,1855-1905),法国作家。

[注3] \omega是希腊字母的最后一个字母,代表终结。如《新约·启示录》中说:“我是阿拉法、我是俄梅戛、我是首先的、我是末后的、我是初、我是终。”(启22:13)阿拉法即\alpha,希腊字母中的第一个,俄梅戛即\omega

[注4] 德语,意为“不可企及者,在此事已成。”

[注5] 德日进(Pierre Teilhard de Chardin,1881-1955),法国思想家,地质学家和古生物学家、天主教耶稣会修士,著作中有关于无限和永恒的论述。

[注6] \aleph是希伯莱文的第一个字母,读作“阿列夫”;\aleph_0就读作“阿列夫零”,其他下标也以此类推。

[注7] 这是乌龟在学神探福尔摩斯的口气半开玩笑地称赞阿基里斯。

[注8] 这里乌龟显然想起了龟兔赛跑的故事。

[注9] 原文直译是“以为自己是拿破仑”,法文俗语,即不知道自己的斤两,脑子有点疯了。这里引用电影《大腕》里的笑话翻译。

[注10] 司汤达综合症是指由于欣赏艺术作品而引起激动情绪后的身体不适,以法国作家司汤达的名字命名。

[注11] 按古希腊神话,当阿基里斯还是婴儿时,他的母亲忒提斯曾握住他的脚踵,倒提着将他在冥河水中浸泡过,使他全身刀枪不入,只有被捏住的脚踵是个例外。在特洛伊战争中,他被暗箭射中脚踵而死。所以“阿基里斯之踵”一词常被用来形容“唯一的致命处”。

[注12] 马赫洛基数以数学家Paul Mahlo的名字命名,它是Mahlo于1911年首先提出的

[【逻辑引擎】注1] 通俗地讲,你可以认为每一个序数就代表它下面按顺序排列的所有比它小的序数的序列。例如序数3就代表(0,1,2),序数\omega就代表(0,1,2,3...),序数\omega+1就代表(0,1,2,3...,\omega)

[【逻辑引擎】注2] 这段话有点晦涩,我稍微解释一下。乌龟试图向阿基里斯说明,即便是看上去非常恐怖的序数\omega^\omega里面的横档的“数量”跟自然数也是完全相等的,可以给其中每一条横档都赋予独一无二的自然数编码。具体怎样做呢?序数\omega^\omega的画中的每一条横档对应的序数都形如:\omega^k a_k + ... + \omega^2 a_2 + \omega a_1 + a_0,其中a_k是自然数,可以对每个这样的序数赋予一个独一无二的自然数编号:{p_k}^{a_k} \times ... \times 5^{a_2} \times 3^{a_1} \times 2^{a_0},其中p_k是第k个素数,p_0=2,p_1=3,p_2=5,...。现在每一个横档都有了一个独一无二的自然数编号,跟自然数之间就建立了一一对应关系,因此也就证明了\omega^\omega这幅画里面的横档数量仍然是可数的。

[【逻辑引擎】注3] 在通常的集合论公理系统ZFC中无法证明这么大的基数的存在性,必须引入断言大基数存在的公理。但这是否跟ZFC相容,根据维基百科直到最近(2006)也无人知道,只知道断言大基数不存在的公理跟ZFC相容。特别巨大的大基数Reinhardt cardinal,已经被证明跟ZFC+j或NBG+AC不相容,而是否能跟ZF+j或NBG相容,根据维基百科直到最近(2006)也无人知道。

【逻辑引擎】维基百科相关条目参考链接:

Ordinal number

Cardinal number

Transfinite number

Limit ordinal

Ordinal arithmetic

Cofinal

Cofinality

Large countable ordinal

Church-Kleene ordinal

First uncountable ordinal

Limit cardinal

Beth number

Regular cardinal

Large cardinal

List of large cardinal properties

Measurable cardinal

Inaccessible cardinal

Mahlo cardinal

Rank into rank

Reinhardt cardinal

Extendible cardinal

Supercompact cardinal

Reflection principle

Vopěnka’s principle

Huge cardinal

Dehornoy order

Stationary set

自然数的Peano公理系统

下面是不引入集合概念的Peano公理系统。由于不引入集合概念,所以归纳公理必须使用二阶逻辑,对任意属性谓词进行量化。

先引入相等关系(同一关系)的定义:
eq0.\forall a. a=a 自反性(reflexive)
eq1.\forall a,b. a=b \Rightarrow b=a 对称性(symmetric)
eq2.\forall a,b,c. a=b \wedge b=c \Rightarrow a=c 传递性(transitive)
eq3.\forall P,a,b. a=b \Rightarrow (P(a)\Rightarrow P(b)) 相等则具有相同属性。

利用上述相等关系定义,这里给出不依赖于集合论只基于二阶逻辑的自然数Peano公理:
n0.N(0) 0是自然数
n1.\forall a. N(a) \Rightarrow N(S(a)) 自然数的后继也是自然数
n2.\forall a,b. N(a) \wedge N(b) \Rightarrow (S(a)=S(b) \Rightarrow a=b) 仅当两自然数相等后继才可能相等
n3.\forall a. N(a) \Rightarrow \sim 0=S(a) 0不是任何自然数的后继
n4.\forall P,a. P(0) \wedge (N(a) \Rightarrow (P(a) \Rightarrow P(S(a))) \Rightarrow (\forall b. N(b) \Rightarrow P(b)) 归纳公理的二阶逻辑版本。对于任意属性P和任意自然数a,如果【a)0具有属性P,b)只要a具有属性P则a的后继也具有属性P】,那么任意自然数都具有属性P。如果引入集合概念就可以只用一阶逻辑。

我求得的全新Einstein场方程精确解

(孙伊2013-12-20于上海交大闵行物理楼)

本文介绍我2011年求得的一个之前未见诸文献的Einstein场方程精确解,它是在远处时空渐进平坦条件下的最一般球对称精确解(注,并非真空或静态的特殊情况,可以处理任何动态非真空情况。以下简称为US解,Universal Spherical)。从US解出发可立即证明Birkhoff定理及其增强版,在静态真空无电荷情况下则立即变成Schwarzschild外部解,代入点电荷电场的能量动量张量则立即变成Reissner-Nordstrom带电球对称解(RN解)。

US解形式如下(具体推导过程请参考我的原始论文JCAP 1101:031,2011或勘误版arXiv:1102.2609):

    \[\large{ds}^2 = -f(r,t)\left(1-\frac{2M(r,t)}{r}\right) {dt}^2+\left(1-\frac{2M(r,t)}{r}\right)^{-1} {dr}^2+r^2 {d\Omega}^2\]

    \[({d\Omega}^2 = {d\theta}^2 + {(\sin \theta)}^2{d\phi}^2)\]

其中f(r,t)M(r,t)的形式后面将给出。有些同学可能会注意到,既然能够描述任意的径向运动,为什么这个解的度规形式里却没有rt交叉项?实际上只要选择适当的坐标就可以做到这一点,不了解这件事的同学可以参考Weinberg的“Gravitation and Cosmology”第11章。

这个解的形式看上去US解的度规形式跟Schwarzschild解很相似,但是项前面多了一个系数f(r,t),且M不再是常数,表示Schwarzschild坐标系中时刻t和半径r之内的总能量(注,这种动态情况下称之为总能量可能不合适。唯一可以肯定的是这是由能量动量张量清晰定义的关于tr的函数,是否能叫做总能量并不重要。):

    \[\large M(r,t)=\int_0^r {4π \tilde{r}^2 \rho(\tilde{r},t)d\tilde{r}}\]

f(r,t)是由密度\rho和径向压强p决定的(注,切向压强p_t不独立于\rhop而被吸收掉了):

    \[ \large f(r,t) = \exp \left\{ -\int_r^\infty 8\pi\tilde{r} \left(1-\frac{2M(\tilde{r},t)}{\tilde{r}}\right)^{-1} \left(\rho(\tilde{r},t)+p(\tilde{r},t)\right)d\tilde{r} \right\} \]

聪明的同学一眼就能看出来,不带电球对称星球的外部真空区\rho(\tilde{r},t)=p(\tilde{r},t)=0,所以f(r,t)=1,由能量守恒可知在外部真空区M是常数,立即回归到Schwarzschild解:

    \[\large{ds}^2 = -\left(1-\frac{2M}{r}\right) {dt}^2+\left(1-\frac{2M}{r}\right)^{-1} {dr}^2+r^2 {d\Omega}^2\]

这其实就是Birkhoff定理:无论球对称星球内部的物质有怎样的径向运动,外部真空区一定满足Schwarzschild外部解。

带电球对称星体的外部真空存在球对称静电场,该静电场的能量密度和压力分别为:

    \[\rho(r)=\frac{Q}{8\pi r^4},p(r)=\frac{-Q}{8\pi r^4}\]

于是仍然有\rho(\tilde{r},t)+p(\tilde{r},t)=0,所以也仍然有f(r,t)=1,而

    \[\large \begin{array}{ll} M(r) &\displaystyle = \int_0^r 4\pi \tilde{r}^2 \rho(\tilde{r},t)d\tilde{r}\\ &\displaystyle = \int_0^\infty 4\pi \tilde{r}^2 \rho(\tilde{r},t)d\tilde{r} - \int_r^\infty 4\pi \tilde{r}^2 \rho(\tilde{r},t)d\tilde{r}\\ &\displaystyle = \mathcal{M} - \frac{\mathcal{Q}^2}{2r} \end{array} \]

注,上式中的\mathcal{M},是全空间总能量,包括全空间的电场能,而\frac{\mathcal{Q}^2}{2r}是半径r以外的总电场能。

这澄清了我之前多年的一个误解:我原以为RN解中那个\mathcal{M}是不包括全空间电场能的,于是如果电荷量特别大以至于\mathcal{Q}>\mathcal{M},奇点就会裸露。现在知道\mathcal{M}是包括全空间电场能的总能量,就算带电粒子除了静电能以外的质量等于0,也不过会使\mathcal{Q}=\mathcal{M},绝不会出现\mathcal{Q}>\mathcal{M}的情况。

现在我们直接得到了带电球对称星球的Reissner-Nordstrom解:

    \[\large{ds}^2 = -\left(1-\frac{2\mathcal{M}}{r}+\frac{\mathcal{Q}^2}{r^2}\right) {dt}^2+\left(1-\frac{2\mathcal{M}}{r}+\frac{\mathcal{Q}^2}{r^2}\right)^{-1} {dr}^2+r^2 {d\Omega}^2\]

这其实是Birkhoff定理的增强形式:无论球对称带电星球内部的物质有怎样的径向运动,外部包含电场的真空区一定满足Reissner-Nordstrom解。

当然,US解不仅能在附加条件下导出上述真空静态解以及诸如理想不可压缩流体球之类的非真空静态解,还能处理非真空区物质的任意径向运动。

我最初求US解的目的是试图处理黑洞蒸发,试图弄清落向蒸发黑洞的物体会经历什么。之前已知的所有非真空球对称精确解都是静态解,而落向蒸发黑洞的物体会置身其辐射场,而辐射场是动态的,所以之前已知的所有精确解都无法处理这种情况。我最终用US解证明只要球对称黑洞的寿命因蒸发而有限,那么无论蒸发过程多复杂,时间多漫长,广义相对论都会禁止任何物体在黑洞蒸发消失之前落入该黑洞。而作为一个逻辑结论,如果形成了的黑洞会蒸发,那么引力坍塌就无法形成黑洞。这件有趣的事以后再讲。

感兴趣的同学可以用Mathematica将US解带入Einstein场方程进行检验,Mathematica程序:BH-Code

附1,球对称条件下能量动量张量{T_\mu}^\nu的非零项:

    \[ \begin{array}{ll} {T_t}^t & = (\partial_r M)/(4\pi r^2 )=\rho\\ {T_r}^r & = p\\ {T_t}^r & = (\partial_t M)/(4\pi r^2 )\\ {T_\Omega}^\Omega & = p_t \end{array} \]

其中{T_\Omega}^\Omega = p_t是切向压力,{T_t}^r是径向能流密度(也是动量密度)

注,在球对称情况下,切向压力p_t不独立于密度\rho和径向压力p,可由\rhop唯一确定,因为切向压力和径向压力共同决定了该处物质的径向加速度。切向压力的具体表达式相当复杂。

附2,下图显示了Einstein场方程部分已知精确解之间的关系,包括我给出的US解:
!exact-solutions

黑洞,要么无法形成,要么不会蒸发。

我2011年在在JCAP上发表了一篇文章:Black hole — never forms, or never evaporates

链接: JCAP, arXiv, DOI, Scholars Portal Journals

我手中未经JCAP排版的修订版,纠正了一些笔误和语法问题:Black hole — never forms, or never evaporates

我的计算表明,如果黑洞会因蒸发而寿命有限(无论其寿命是多么不可思议地漫长),都没有任何物质能够在其蒸发消失之前落入其视界。而这样一来,只要存在蒸发机制,那么真实黑洞就会由于这种机制的存在而无法形成,理论物理学中那个信息丢失困难也不复存在,甚至经典广义相对论中的奇点疑难也会被自然地避免。

除了结论,文中还给出了Einstein Field Equation最一般的球对称解,任何(远方渐进平坦的)球对称解都是其特例,包括Schwarzschild,Reissner-Nordstrom,静态流体球,除此之外还覆盖了任何球对称的动态非真空情况。

这是验证这个最一般球对称解的Mathematica代码:!BH-Code

解释一下扩散方程

(各向同性的)扩散方程:

    \[\frac{\partial\phi(\vec{r},t)}{\partial t} = \nabla \cdot \big[ D(\phi,\vec{r}) \ \nabla\phi(\vec{r},t) \big]\]

\phi(\vec{r},t)是某点某时刻的浓度,D(\phi,\vec{r})是某点在浓度\phi下的扩散系数。如果扩散系数D是常数,那么扩散方程退化为热传导方程:

    \[\frac{\partial\phi(\vec{r},t)}{\partial t} = D\nabla^2\phi(\vec{r},t)\]

扩散方程很好理解,方程中D(\phi,\vec{r}) \ \nabla\phi(\vec{r},t)就是(负的)扩散过程中的浓度流。某点某时刻浓度流的大小等于该点的(负的)浓度梯度乘以扩散系数。
而(负的)浓度流的散度自然就是浓度随时间的变化率。

事实上扩散方程是可以直接从连续性方程得出的:

    \[\frac{\partial\phi}{\partial t}+\nabla\cdot\mathbf{j}=0\]

如果浓度流正比于该点的(负的)密度梯度(Fick’s law),那么:

    \[\mathbf{j}=-D(\phi)\,\nabla\phi(\vec{r},t)\]

直接带入连续性方程就给出了扩散方程。

对于各向异性扩散,浓度流的方向跟(负的)浓度梯度的方向可能并不重合,此时扩散系数就必须是一个张量,相应的矩阵是对称正定的。

    \[\frac{\partial\phi(\vec{r},t)}{\partial t} = \sum_{i=1}^3\sum_{j=1}^3 \frac{\partial}{\partial x_i}\left(D_{ij}(\phi,\vec{r})\frac{\partial \phi(\vec{r},t)}{\partial x_j}\right)\]

参见:
https://en.wikipedia.org/wiki/Diffusion_equation

对一道关于三扇门赌局的概率问题的解答

善科问答上提到了一道多年前曾经引起了广泛关注的概率问题,这个问题已经被很好解决了,但可能很多人并不清楚完整的解答,甚至多年来仍然坚信当年他所认定的某个答案。

以下是善科问答上的原文引用
————————————————————————————
玛丽莲(Marilyn vos Savant,维基链接)是迄今为止最高智商的吉尼斯世界纪录保持者,她出过一道“羊和汽车”问题,曾引起美国公众的广泛关注:

假如有三扇门,其中一扇门后是一部汽车,另外两扇门后各有一头山羊。你的任务是选中那扇有汽车的门(选中就能开回家啦)。当你随机选择了一扇门,这时主持人在剩下两扇门中打开一扇后面有羊的门,并问你:“为了有较大的机会赢得汽车,你是坚持原来的选择、还是改选另一扇门呢?”

你会怎么决定呢?改选与否对你最后赢得汽车的概率有何影响呢?
————————————————————————————

这道题是一个引人思考的好问题,但由于题目条件不足所以是个错题。

主持人行为的策略对题目结果有至关重要的影响,但该题目中你完全无法确定主持人的策略,所以也无法确定换选得车的概率。

主持人的可能策略:
1.无论你是否选中车,他都会打开另一扇没车的门。(此时换选就是2/3得车)
2.只要你没选中车,他就会打开另一扇没车的门。(此时换选就是100%得车)
3.只要你选中了车,他就会打开另一扇门。(此时换选就必然没车)
4.以上策略的概率混合策略……(根据不同的混合,换选会有不同的概率得车)

如果你完全不能判断主持人的策略,那么事实上你也不能完全确定换选之后得车的概率。

许多稍微接触过一点概率论的同学往往会有如下错觉:即便不能明确预言结果,计算可能结果的概率总是可能的。
这个直觉完全是错的,如果你不能事先确定问题的概率模型,那么你根本就无法对可能结果的概率做准确计算。
而上述这个问题中主持人的策略是概率模型中不可或缺的部分。

当然,你可以根据先前主持人的行为或其他信息对主持人会采取哪种策略的可能性进行估计,当你对此作出了估计之后,就可以对这个问题建立概率模型了。

事实上,对概率论的肤浅理解在许多时候会导致荒谬的结果。例如某些贝叶斯主义者会利用贝叶斯公式估计上帝存在和不存在的概率。事实上,如果你想要用贝叶斯公式和样本数据来估计某件事情发生的概率,首先要求这个时间的发生确实有一个明确的概率p,只是你事先并不知道这个p等于什么,只能通过样本数据对这个p做统计估计。但你能说上帝存在这件事情具有某个明确的概率p么?这是什么意思?难道你的意思是说:在每一个采样时刻,上帝存在的概率是p,不存在的概率是1-p,于是某些时刻做采样时上帝刚好存在,另一些时刻做采样时上帝刚好不存在,于是只要积累足够多的样本,我们就能越来越可靠地估计出在每一次采样时上帝存在的概率了?

一本好书中流露出的傲慢与偏见

尼古拉斯·塔勒布的《黑天鹅》总体上应该是一本好书,但不巧我第一次看到的是书中的一段设计对白,把我给恶心到了。

————————————————————————————
我知道,肥佬托尼与约翰博士几乎没机会出现在同一地方,更不要说在一起泡吧,所以不妨把这当做一个思想实验。我将问他们一个问题,然后比较他们的答案。

尼古拉斯:假设有一个公平的硬币,抛掷后出现正反面的概率各有50%。我连续掷了99次都是正面。那么,我第100次抛掷硬币出现反面的概率有多大?
约翰博士:太简单了!当然是50%,既然你已经假设硬币正反面各有50%的概率且每次抛掷相互独立。
尼古拉斯:你的答案呢,托尼?
肥佬托尼:我会说不超过l%.这是显然的。
尼古拉斯:为什么?我假定是硬币是公平的,每面都有50%的概率。
肥佬托尼:如果你相信所谓“50%”的说法,你要么是个草包,要么是个傻子。这枚硬币里面一定做了手脚,不可能是公平游戏。(也就是说,在硬币抛出99次,每次都得到正面的情况下,你对公平性的假定很可能是错误的。)
尼古拉斯:但约翰博士说是50%。
肥佬托尼(在尼古拉斯耳边小声说):我在银行的时候就知道这些傻瓜。他们的思维太迟钝了,你可以利用他们。
现在,这两个人你更希望谁当纽约市市长?约翰博士完全在条条框框里面思考——别人给他的条条框框,肥佬托尼则几乎完全在条条框框以外思考。
————————————————————————————
(接下来是我续的一段)
逻辑引擎:你傻逼啊,有扔一百次硬币的时间都泡到好几个马子了。
尼古拉斯:我们只是在做概率题啊。
逻辑引擎:如果你以为你们在做概率题,你要么是个草包,要么是个傻子。做题能随便扔掉题目的前提条件么?
尼古拉斯:但肥托尼确实是在解答问题啊。
逻辑引擎(在尼古拉斯耳边小声说):我在公司里见过这些傻瓜。他们自以为很聪明,看到有人正按规则做事就以为别人是只会循规蹈矩的傻瓜并加以嘲笑,这种人特别好忽悠,你随便拍拍马屁夸他们聪明绝顶就可以无偿利用他们。
现在,这两个人你更希望谁当纽约市市长?肥佬托尼完全在条条框框里面思考——别人给他的条条框框,还沾沾自喜地自已为跳出了框框,逻辑引擎则几乎完全在条条框框以外思考。
————————————————————————————

我当然知道作者要表达什么意思,我也见过那些只会循规蹈矩做事的笨蛋,其中有些人当年还是学校里的尖子生。但作者的例子构造得实在是很犯贱,为什么不能直接拿实际的问题举例子而是拿做数学题来举例子呢?如果真要玩跳出框框的游戏,知道什么时候守规则的人比只会跳出框框还沾沾自喜的人跳得更远。其实这反映了许多人根深蒂固的傲慢与偏见,而作者在书中显然也不经意流露出了这种情绪。

【数学科普】数系为什么要一次又一次地扩充?

自然数、整数、有理数、代数数、实数、复数,数学家们为什么要一次又一次地扩充数系呢?

这里你将遇到一个关键词:『封闭』。我们说数系对某个运算是『封闭』的,意思是任何属于该数系的数经该运算后得到的结果仍属于该数系,例如实数系对于加减法运算都是封闭的。如果一个数系对某运算不封闭,那每当你使用该运算时,就要分条件讨论运算结果是否仍属于该数系。这对于单一的运算还不是特别严重的问题,但如果一个表达式包含了许多该运算的步骤,条件分支的组合数量就可能会指数爆炸。所以,如果我们能设法使数系对一个运算封闭,就可以放心大胆地在表达式中使用该运算而无需分条件讨论。

从最简单的例子开始,假设我们有一个有限的数系,只包含三个数{1,2,3},这个可怜的数系对『后继』这个简单运算都不封闭,3的后继显然不属于{1,2,3}这个数系。我们可以扩充这个有限的数系使之对后继运算封闭,这样我们就可以引入自然数(其实还有别的方案,例如把这些数字排列成一个圈,这种结构也是数学家和工程技术中常用的,但这种结构缺少自然数所具备的另一些有用性质,并不能取代自然数,本文对此也不再深入讨论,有兴趣的同学可以学习高等代数)。任何自然数的后继仍是个自然数,所以自然数对后继运算是封闭的。有了对后继运算封闭的自然数,我们还可以基于后继运算进一步定义加法和乘法。自然数不但对后继运算封闭,对加法和乘法也都封闭,任意两个自然数相加或相乘仍是自然数。但自然数对后继的逆运算(前驱)并不封闭,1没有前驱,这使自然数对加法的逆运算(减法)也不封闭,此外自然数对乘法的逆运算(除法)也不封闭。为了对前驱和减法封闭,就需要将自然数扩充为整数;为了对除法封闭,就需要将自然数扩充为·正·有理数。这两项扩充放在一起,我们就有了有理数这个数系。很不幸,我们无法无矛盾地将自然数扩充为对减法和除法两个运算同时封闭的数系,有理数(包括正有理数负有理数和0)对减法封闭,但必须去掉0才能对除法封闭,虽然有这个不便导致有时候我们不得不分条件讨论除以0的情况,但在许多情况下这并不困难,因此除了遇到可能除以0的情况,我们仍然可以放心大胆地在有理数中使用四则运算(加减乘除)表达式而无需太多讨论太多条件分支。

有了乘法运算就可以定义乘方运算,在我们解涉及未知数乘方的方程时就遇到了开方运算。古希腊毕达哥拉斯学派的数学家希帕索斯证明任何有理数的平方都不等于2(证明很简单有兴趣的同学可以搜搜看),虽然能找到平方任意靠近2的有理数。不但如此,也不存在平方等于-1的有理数。古代数学家曾经长期认为对负数开偶次方没有意义,因此最初并没有尝试建立一个对开方运算完全封闭的数系,只想建立一个除了对负数开偶次方之外的情况封闭的数系,例如由有理数通过有限次四则运算和乘方开方运算(负数开偶次方除外)任意复合运算得到的数,不妨称为根式数(无正式名称),以及所有整系数代数方程的实根构成的·实·代数数(比根式数的数系更大),但正由于这些数系都不能对开方运算完全封闭,以至于连三、四次方程求根公式都需分若干情况讨论,极为不便,以至于在数学中用得并不多。后来的突破是建立了对负数开方也保持封闭的数系,也就是(复)代数数,该数系对于开任意次方运算都完全封闭,任意整系数代数方程在该数系中都具有数量与方程次数相同的根,而且对四则运算的支持和有理数一样好,完全可以取代根式数和·实·代数数。

到了这里,我们首先提到了(复)代数数,却还没有提到实数,这跟中小学数学教育过程不同,中小学是先学了实数(但并未澄清实数是什么),然后才学复数。不过实数系的建立确实超出了小学初中的数学水平,是现代数学分析的基础。前面提到了乘方运算的逆运算,开方运算,也就是已知幂和指数求底数的运算,但乘方运算还有另一个逆运算,已知幂和底数求指数,我们前面谈到的任何一个数系对这个运算都不封闭,但数学家们没有专门为了封闭这个运算而扩充前面提到的数系,柯西和他同时代的数学家们走了另一条路,也能顺带解决对数运算和一大堆其他运算的封闭性。当时的数学家已经需要大量处理极限和微积分的问题了,他们需要数系在极限运算下仍然保持封闭。柯西定义了一种今天被称为柯西序列的东西,不太严格地说,只要在这个序列的前面去掉有限但足够多的元素之后,剩下的任意两个数的距离都不超过事先给定的任意小的正数。一个无限逼近根号2的有理数序列就是这样一个柯西序列,但这个序列最终逼近的根号2并不属于有理数,所以有理数对柯西序列求极限的运算并不封闭。事实上很容易证明代数数也不能对柯西序列求极限的运算收敛,虽然代数数包括根号2之类的数。而一个数系对柯西序列求极限的运算收敛是保证能够在这个数系上正确地做微积分的前提条件,『实数』就是满足这种要求的数系,但其严格基础直到19世纪末才由康托和戴德金建立。『实数』这个名字其实非常误导,最初这个名字仅仅是为了跟『虚数』加以区别,二者合称复数,那个时候实数和复数的真正含义特指前面提到的实代数数和(复)代数数,跟柯西序列求极限的运算没有直接关系。但由于很长一段时间微积分等数学分析工作没有涉及复数,所以『实数』这个名字后来就演变为由(实)有理数扩充而满足对柯西序列求极限的运算封闭的数系,也就是今天的实数。把这个扩充推广到复代数数中,就得到了今天意义上的复数。于是人们在复数上也建立了数学分析——复分析。许多实分析中不太优雅的定理和公式在复分析中都有简洁漂亮的推广。

再前面的每一次数系扩充过程中,扩充后的数系对原数系中本来就封闭的运算继续保持封闭,并且增加了新的封闭运算。因此无论是实数还是复数,对四则运算的支持都跟有理数一样好,我们可以轻松地在实数和复数中书写四则运算式,而除了“除以0”之外什么都不用担心。

至此,我们囫囵吞枣地介绍了数系扩充的过程,从有限数{1,2,3}一直扩充到实数和复数。这个扩充过程中,人们并不仅仅满足于使数系对某些运算封闭,还详细研究了数系扩充之后带来的新性质,其中许多性质都非常有用。比方说,复数可以表示为实部和虚部两部分,还可以表示为幅值和极角,而这种表示对指数和三角函数运算会带来许多意想不到的便利。另一方面,实部和虚部这种表示方式还可以对应到平面上的点,所以用复数来处理平面上的问题也往往会带来便利。但不要以为复数仅仅是平面上的矢量,虽然复数的加法对应矢量加法,但复数的乘积并不对应矢量的乘积运算。建立复数是为了处理代数方程求根的问题,而处理平面向量问题只是复数带来的意外收获。处理一般的向量问题更方便的工具是向量分析。

有人可能会问,复数是否还能进一步扩充,处理更高维的问题?这个问题无法简单地回答。事实上,已经有人把复数扩充为四元数八元数十六元数等,都是一种叫Clifford代数的子代数,但这些扩充跟我们之前提到的扩充很不相同。数系的每一次扩充都会破坏原有数系的部分性质,例如任何两个自然数之间的自然数是有限的,但有理数不具备这个性质,有理数是可数的,但实数不是……,但我们特别关心的四则运算的一些基本性质,乘法和加法的交换性和结合性,以及乘法和加法的分配律,在我们前面的扩充过程中从未受到破坏。但四元数乘法不满足交换性,八元数乘法不满足交换性和结合性(但满足一种叫“交错性”的比结合性更弱的性质),而十六元数的乘法连交错性都不满足。也就是说,确实可以进一步扩充复数,但四则运算的一些我们很关心的性质会受到破坏。已经有人证明,对复数的进一步扩充无法保证四则运算的所有这些性质。

数系

图中给出了从自然数开始,不断封闭更多运算所得到的数系,直到复数。

又一个巨大的数学反例

反例:
Let f(n) = GCD(n^17+9, (n+1)^17+9), then f(n) = 1 for all n < = 8424432925592889329288197322308900672459420460792432 but f(8424432925592889329288197322308900672459420460792433) = 8936582237915716659950962253358945635793453256935559 > 1

形式对称的Fourier transform

从Wikipedia: Fourier transform上看到的:

    \[ \hat{f}(\xi) = \int\limits_{-\infty}^{+\infty}\, e^{-2\pi i x\xi}\, f(x)\, dx \]

    \[ f(x) = \int\limits_{-\infty}^{+\infty}\, e^{+2\pi i\xi x}\, \hat{f}(\xi)\, d\xi \]

由此:

    \[ \delta(x)= \int\limits_{-\infty}^{+\infty}\, e^{2\pi i\xi x}\, d\xi \]

    \[ f(x) = \int\limits_{-\infty}^{+\infty}\, \delta(x-y)\, f(y)\, dy \]

    \[ (f \star g)(t) \stackrel{\mathrm{def}}{=}\, \int_{-\infty}^{+\infty} f(\tau)\, g(t - \tau)\, d\tau = \int_{-\infty}^{+\infty} f(t-\tau)\, g(\tau)\, d\tau \]

卷积定理:

    \[ \mathcal{F}(f \star g) =  \mathcal{F} (f) \cdot \mathcal{F} (g) \]

其中\mathcal{F}是Fourier变换。
微分定理:

    \[ \mathcal{D}(f \star g) = \mathcal{D}f \star g = f \star \mathcal{D}g \]

其中\mathcal{D}是微分算子。

Benford’s Law

Benford’s Law

我们平常所遇到的各种非零的数字之中(例如各种物理、数学常数),首位非零数字是1、2、3……9的概率都相同么?感觉上似乎如此,但实际上并不是这样,采用r进制时,首位数字为k(0<k<r)概率差不多是log_r(k+1) - log_r(k) = log_r \frac{k+1}{k}。这就是所谓Benford’s Law。

Wikipedia上有这个法则的若干种解释:

<Benford’s Law>

一个比较直观的解释是:当我们改换单位制时,首位数字的分布应该不变,这就是所谓scale invariance。如何分布才能保证这一点呢?由于我们考虑的是非零的数字,那么总可以将数字写成[1,10)的有效数字部分x乘以10的某个指数(科学计数法)。扔掉10的指数,对有效数字x取以10为底的对数,就得到[0,1)区间分布的一个数y=log_{10}x,假设y的分布密度函数为f(Y)。如果我们改变单位制,就相当于将x乘上一个常数c,如果乘积cx大于等于10,就得再次约化到[1,10)区间,这相当于把y循环右移了log_{10}c,分布函数f(Y)在这种循环右移的情况下应该保持不变,由于循环右移的偏移量是任意的,所以概率密度f(Y)必须是[0,1)上均匀分布的。有了这个分布,我们就可以估计首位数字是k的概率了。x的首位数字是k就要求x落在区间[k,k+1),也就是y落在[ log_{10}(k),log_{10}(k+1) ),不失一般性,用r进制代替10进制,首位数字是k的概率就是log_r(k+1) - log_r(k) = log_r \frac{k+1}{k}

转载,数学反例

千万不要迷信规律:大反例合集

wwwckq 发表于 2011-7-27 10:59:00

 

        数学猜想并不总是对的,错误的数学猜想不占少数。关键在于,有时反例太大,找出反例实在是太困难了。这篇日志收集了很多大反例的例子,里面提到的规律看上去非常诱人,要试到相当大的数时才会出现第一个反例。

千万不要迷信规律

      圆上有 n 个点,两两之间连线后,最多可以把整个圆分成多少块?

      

       上图显示的就是 n 分别为 2 3 4 的情况。可以看到,圆分别被划分成了 2 块、 4 块、 8 块。规律似乎非常明显:圆周上每多一个点,划分出来的区域数就会翻一倍。


事实上真的是这样吗?让我们看看当 n = 5 时的情况:

      

       果然不出所料,整个圆被分成了 16 块,区域数依旧满足 2n-1
的规律。此时,大家都会觉得证据已经充分,不必继续往下验证了吧。偏偏就在 n = 6 时,意外出现了:

      

      此时区域数只有 31 个。

最有名的素数生成公式

       1772 年,Euler 曾经发现,当 n 是正整数时, n2 + n + 41 似乎总是素数。事实上,n 1 一直取到 39,算出来的结果分别是:

43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281,
313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853,
911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601

        这些数全都是素数。第一次例外发生在 n = 40 的时候,此时 402 + 40 + 41 = 402 + 40 + 40 + 1 = (40 + 1)(40 + 1) = 41 × 41

xn – 1 的因式分解

    x2 – 1 分解因式后等于 (x + 1)(x – 1) x20 – 1 分解因式后等于

(x – 1) (x + 1) (x2 + 1) (x4 – x3 + x2 – x + 1) (x4 + x3 + x2 + x + 1) (x8 – x6 + x4 – x2 + 1)

        对于所有的正整数 n xn – 1 因式分解后各项系数都只有可能是 1 或者 -1 吗?据说有人曾经算到了 x100 – 1 ,均没有发现反例,终于放心大胆地做出了这个猜想。悲剧的是,这个猜想是错误的,第一个反例出现在 n = 105 的情况, x105 – 1 分解出来等于

(x – 1) (x2 + x + 1) (x4 + x3 + x2 + x + 1) (x6 + x5 + x4 + x3 + x2 + x + 1)
(x8 – x7 + x5 – x4 + x3 – x + 1) (x12 – x11 + x9 – x8 + x6 – x4 + x3 – x + 1)
(x24 – x23 + x19 – x18 + x17 – x16 + x14 – x13 + x12 – x11 + x10 – x8 + x7 – x6 + x5 – x + 1)
(x48 + x47 + x46 – x43 – x422 x41 – x40 – x39 + x36 + x35 + x34 + x33 + x32 + x31 – x28
– x26 – x24 – x22 – x20 + x17 + x16 + x15 + x14 + x13 + x12 – x9 – x82 x7 – x6 – x5 + x2 + x + 1)

2 为底的伪素数

      下面是当 n 较小的时候, n 2n – 2 的值。

      

       似乎有这样的规律: n 能整除 2n – 2 ,当且仅当 n 是一个素数。如果真是这样的话,我们无疑有了一种超级高效的素数判定算法( 2n
可以用二分法速算,期间可以不断模 n )。国外数学界一直传有中国人 2000 多年前就发现了这一规律的说法,后来发现其实是对《九章算术》一书的错误翻译造成的。再后来人们发现,这个规律竟然是错误的。第一个反例是 n = 341,此时 341 能够整除 2341 – 2 ,但 341 = 11 × 31

       事实上,根据 Fermat 小定理,如果 p 是素数,那么 p 一定能整除 2n – 2。不过,它的逆定理却是不成立的,上面提到的 341 便是一例。我们把这种数叫做以 2 为底的伪素数。由于这种素数判定法的反例出人意料的少,我们完全可以用它来做一个概率型的素数判定算法。事实上,著名的
Miller-Rabin
素性测试算法就是用的这个原理。

Perrin 伪素数

       定义 f(n) = f(n – 2) + f(n – 3) ,其中 f(1) = 0 f(2) = 2 f(3) = 3 。这个数列叫做 Perrin 数列。

      

       似乎有这么一个规律: n 能整除 Perrin 数列的第 n f(n) ,当且仅当 n 是一个素数。如果这个规律成立的话,我们也将获得一个效率非常高的素数检验方法。根据
MathWorld
的描述,1899 Perrin 本人曾经做过试验,随后 Malo 1900 年, Escot 1901 年,以及 Jarden 1966 年都做过搜索,均未发现任何反例。直到 1982 年, Adams Shanks 才发现第一个反例 n = 271 441 ,它等于 521 × 521 ,却也能整除 f(271 441) 。下一个反例则发生在 n = 904 631 的时候,再下一个反例则是 n = 16 532 714 。这种反例被称为 Perrin 伪素数。

最经典的大反例

      说到大反例,这是我最喜欢举的例子。下面是大于 1 的正整数分解质因数后的结果:

2 = 2
3 = 3
4 = 2 × 2
5 = 5
6 = 2 × 3
7 = 7
8 = 2 × 2 × 2
9 = 3 × 3
10 = 2 × 5

       其中,46910 包含偶数个质因子,其余的数都包含奇数个质因子。你会发现,在上面的列表中一行一行地看下来,不管看到什么位置,包含奇数个质因子的数都要多一些。 1919 年,George Pólya 猜想,质因子个数为奇数的情况不会少于 50% 。也就是说,对于任意一个大于 1 的自然数 n ,从 2 n 的数中有奇数个质因子的数不少于有偶数个质因子的数。这便是著名的 Pólya 猜想。

        Pólya 猜想看上去非常合理——每个有偶数个质因子的数,必然都已经提前经历过了有奇数个质因子这一步。不过,这个猜想却一直未能得到一个严格的数学证明。到
1958 年,英国数学家 C. B. Haselgrove 发现, Pólya 猜想竟然是错误的。他证明了 Pólya 猜想存在反例,从而推翻了这个猜想。不过,Haselgrove 仅仅是证明了反例的存在性,并没有算出这个反例的具体值。Haselgrove 估计,这个反例至少也是一个 361 位数。

        1960 年,R. Sherman Lehman 给出了一个确凿的反例:n = 906 180 359。而 Pólya 猜想的最小反例则是到了 1980 年才发现的:n = 906 150 257

Fermat 大定理还能推广吗?

       Fermat 大定理说,当 n > 2 时,方程 xn + yn = zn
没有正整数解。 Euler 曾经猜想,当 n > k 时,方程 x1n + x2n + … + xkn = yn
都没有正整数解。 1986 年,Noam Elkies 给出了方程 x4 + y4 + z4 = w4
的一个正整数解,从而推翻了这个猜想。这个反例是:2 682 4404 + 15 365 6394 + 18 796 7604 = 20 615 6734

XX 型平方数

      11, 22, 33, 44, 55, 66, 77, 88, 99, 1010, 1111, 1212, … 都不是完全平方数。有没有什么数,把它连写两次后,正好是一个完全平方数呢?有。第一个这样的数是 13 223 140 496 ,把它连写两次将得到 1 322 314 049 613 223 140 496 ,是 36 363 636 364 的平方。第二个这样的数则是 20 661 157 025 ,它对应了 45 454 545 455 的平方。更多信息可见
http://oeis.org/A102567

总是相等吗?

      下面是 n 为正整数时, 2 / (21/n – 1) 取上整的结果与 2n / ln(2) 取下整的结果:

      

       这两者的结果总是相等吗?不是的。第一个反例是 n = 777 451 915 729 368,前者算出来的结果是 2 243 252 046 704 767 ,但后者是 2 243 252 046 704 766 。下一个反例则出现在 n = 140 894 092 055 857 794 的时候。更多信息可见
http://oeis.org/A129935

至今仍未找到的反例

       有没有什么猜想,明明已经被推翻了,所有人都知道存在反例,但因为反例实在是太大了,直到现在仍然没有找到呢?有。下面这张表展示了 n 取不同值时 pi(n) li(n) 的值,其中 pi(n) 表示不超过 n 的素数的个数,li(n) 则是对数积分0n dx/ln(x)

      

       pi(n) 是否永远小于 li(n) 呢?1914 年,Littlewood 证明了存在一个大数 n 使得 pi(n) ≥ li(n) ,不过却并没有给出一个具体的 n 值来。1955 年,Skewes 给出了这样的 n 值的一个上界:在 10^(10^(10^963)) 以内,必有一个满足 pi(n) ≥ li(n) n

      虽然数学家们正在不断地改进上界(目前的上界大约是 e727.9513
),但仍然无法找出一个具体的 n 来。原因很简单——这个反例实在是太大了。

主要来源:
http://redd.it/iikk4
http://www.guokr.com/article/9688/
http://mathoverflow.net/questions/15444

如果你对此感兴趣,不要错过数学史上的一篇经典论文:The Strong Law of Small Numbers

这篇日志今后将不断更新……

连转带评:纽科姆悖论

有人在新繁星客栈上提到了这个悖论,并且点名叫我帮忙解答。我完全没觉得这个悖论有任何难度,但还是将这个悖论贴在我这里供大家娱乐消遣。
后面是我在新繁星客栈的答复,有所改动。

原文链接

一直没搞懂:纽科姆悖论
或者叫:“外星人悖论”

M:一天,一个由外层空间来的超级生物欧米加在地球着陆。

M:欧米加搞出一个设备来研究人的大脑。他可以十分准确地预言每一个人在二者择一时会选择哪一个。

M:欧米加用两个大箱子检验了很多人。箱子A是透明的,总是装着1千美元。箱子B不透明,它要么装着1百万美元,要么空着。

M:欧米加告诉每一个受试者。

欧米加:你有两种选择,一种是你拿走两个箱子,可以获得其中的东西。可是,当我预计你这样做时,我就让箱子B空着。你就只能得到1千美元。

欧米加:另一种选择是只拿一个箱子B。如果我预计你这样做时,我就放进箱子B中1百万美元。你能得到全部款子。

M:这个男人决定只拿箱子B。他的理由是——

男:我已看见欧米加尝试了几百次,每次他都预计对了。凡是拿两个箱子的人,只能得到l千美元。所以我只拿箱子B,就可变成一个百万富翁。

M:这个女孩决定要拿两个箱子,她的理由是——

女:欧米加已经做完了他的预言,并已离开。箱子不会再变了。如果是空的,它还是空的。如果它是有钱的,它还是有钱。所以我要拿两个箱子,就可以得到里面所有的钱。

M:你认为谁的决定最好?两种看法不可能都对。哪一种错了?它为何错了?这是一个新的悖论,而专家们还不知道如何解决它。

这个悖论是哲学家经常争论的很多预言悖论中最新的,也是最棘手的。它是物理学家威廉·纽科姆发明的,称为纽科姆悖论。哈佛大学的哲学家罗伯特·诺吉克首先发表并分析了这个悖论。他分析的依据主要是数学家称之为“博弈论”或“对策论”的法则。

男孩决定只拿B箱是很容易理解的。为了使女孩的论据明显起来,要记住欧米加已经走了。箱子里也许有钱,也许空着,这是不会再改变的。如果有钱,它仍然有钱;如果空着,它仍然空着。让我们思考一下这两种情况。

如果B中有钱,女孩只拿箱子B,她得到1百万美元。如果她两个箱子都要,就会得到1百万加1千元。

如果B箱空着,她只拿B箱,就什么也得不到。但如果她拿两个箱子,她就至少得到1千美元。

因此,每一种情况下,女孩拿两个箱子都多得1千元。

这条悖论,是试验一个人是否相信自由意志论的“石蕊试纸”类型的悖论。对这个悖论的反应公平地区分出,愿意拿两个箱子的是自由意志论信徒,愿意拿B箱者是决定论(宿命论)信徒。而另一些人则争辩道:不管未来是完全决定的,还是不是完全决定的,这个悖论所要求的条件却是矛盾的。

对这些争论观点的讨论可参见马丁·加德勒在1973年《科学美国人》7月号的数学游戏专栏,以及诺吉克教授发表在同一刊物1974年3月号同一专栏的文章。由于这一悖论还未解决,故它是学生讨论的极好课题。你将发现课堂里对这个悖论的反应是活跃的,十分有益的。

——————————————————————————————
我的解答:

这条悖论,是试验一个人是否相信自由意志论的“石蕊试纸”类型的悖论。对这个悖论的反应公平地区分出,愿意拿两个箱子的是自由意志论信徒,愿意拿B箱者是决定论(宿命论)信徒。而另一些人则争辩道:不管未来是完全决定的,还是不是完全决定的,这个悖论所要求的条件却是矛盾的。

这段评论,看了我后面的分析就可以知道全是一派胡言。我不懂什么叫自由意志论什么叫宿命论,我一个人就可以得出几种不同的答案。而且这个悖论的条件并不是自相矛盾的,而是问题的条件根本就不完备,以至于加入不同的约束条件就可以产生不同的答案。

先引入几种不同的先知(暂且不管其物理上是否能够存在):

第一类先知:精确地知道未来的一切,包括完全精确地知道自己未来的行为。这是个『只读』的先知,他有能力精确预知整个世界的未来,但却完全无法对世界施加任何一丝一毫的影响,甚至完全无法对自己的行为做一丝一毫的改变。这样的先知无法『选择』告诉别人未来会发生什么(当然,他可能预测到自己把未来告诉别人,于是他就只能按照自己的预测吧未来告诉别人。但问题是他还可能预测到自己将要告诉别人的信息是错的,但自己却对此无能为力)。这种先知甚至都不能对未来将要发生在自己身上的事情做任何提前准备,比方说预测到有人要在自己背后捅一刀于是很紧张,但他甚至无法让自己的呼吸或心跳加快,无法让每一个神经信号的传递有任何不同。这种先知很悲剧,他只是一个单纯的观察者,不能对世界施加任何影响,甚至无法『选择』让别人知道自己是个先知。

第二类先知:有能力预测未来,但预测完全准确的前提条件是自己也完全精确地按照自己先前的预测行事,但问题是他也可以在任何时刻选择在不精确按照自己先前的预测行事(比方说先前的预测中自己并没有把未来会发生什么告诉别人,但现在却选择告诉别人),那么就会导致未来不再与自己先前的预测精确相同,而且时间越久与先前的预测偏离可能就越大。事实上,他并不一定要把未来告诉别人,就可以对未来造成影响,比方说由于知道了未来,他关于未来的知识发生了变化,于是脑袋里面某些神经电信号改变了,经过一系列连锁反应就会造成对未来的影响。当然,既然不考虑物理上的限制,你也可以进一步假定这个先知可以将对未来的预测信息存储在宇宙之外,这些知识的存储对我们的宇宙绝对不会造成一丝一毫的影响。或者,你可以反过来假定只要这个先知存储关于未来的知识就必然改变其大脑的物理状态以至于必然对世界造成影响。这样一开这第2类先知又可以分成两类,我们不妨称前者为2A后者为2B。

对于先知2A,在他决定完全按照自己的预测行为的时候,他之前对世界的预测就完全准确无需更新。一旦他选择不按照自己事先对自己行为的预测行事,那么从这个时刻起,世界的未来就不再符合其先前的预测,于是他此时就要立即更新自己关于未来的预测知识。于是每当他选择不按照自己先前对自己行为的预测行事,他对未来的预测就会立即更新。比方说先前预测自己并没有将世界的未来告诉别人,而某个时刻他突然决定告诉别人了,那么他对未来的预测就会立即更新。假设这个先知很要面子,不希望别人发现自己说出的话是错的,那么一旦他发现只要自己把预测告诉别人,自己所预测的事情在这个告知行为影响下就不会发生,那么他就会立即改为选择什么都不说,即便在不说的情况下自己对未来的预测本来是对的。什么时候他恰好发现只要自己将预测结果告诉别人,自己预测的事情就会成真,这种情况下它就会精确地按照自己对自己行为的预测行事,包括说出对未来的预测,于是预测成真。

对于先知2B,这个先知也很悲剧,他每一个时刻对未来的预测都会改变其头脑中的知识以至于改变头脑的物理状态,经过连锁反应影响一段时间以后的世界,使世界的未来跟其脑袋里面当前的知识不同,既然如此他此时此刻关于未来的知识立即就得更新,这是造成了一个自反馈回路,如果运气不好,这个先知就会成为一个真正的2B,脑子里看到的未来始终处于疯狂的甚至无限迅速的变化之中。但是,也有可能没有这么糟糕,自反馈回路有可能真的有自洽的不动点,也就是说,他脑袋的状态疯狂地变来变去之后,突然进入这样一个状态,这个状态中他脑袋里关于未来的知识刚好与实际上会发生的未来(包括他自身的未来)完全精确相同,一旦进入这种状态,他的脑袋里面就总是能够准确地看到未来,而且他脑袋状态随时间的演化也确保总是能跟其预测相同。但是一旦进入这种情况,2B先知就蜕化成了A类先知,他无法做出与自己预测不同的事情。

第三类先知:没能力精确预测整个世界的未来,却有能力任意按照自己的随意操纵整个世界,比方说他可以让任何人做任何事而且以为自己真的想做这件事,或者创造各种各样的神迹等等。当然,逻辑矛盾的事情是没法做的,这不是能力问题,而是错误陈述,例如制造一块自己也搬不动的石头。

当然,你也可以编造出其他类型的先知,只要你有本事确保逻辑自洽就可以。

现在,我给感兴趣的同学留一道思考题:试把上述几种先知带入这个所谓纽科姆悖论之中,而且可以几种不同的方式来假设这个先知的动机,然后在每一种情况下分析这个悖论看看会得到什么样的结果。

简单回合制游戏

本文是『吃苹果游戏和简单回合制游戏的通解』的后续。

对于不能简单画出由游戏局面所构成的状态空间时,还有以下分析策略可用:

一种局面,是否先手必胜,取决于先手是否可以经过一步操作就将该局面变为后手必胜局面。如果先手对该局面的每一种可能的单步操作都无法将局面变为后手必胜局面,那么该局面就是后手必胜局面。

在通过倒推的方法分析回合制游戏必胜策略的时候,凡是后手必胜策略的局面,所有可以通过一步操作就到达该局面的局面都是先手有必胜策略的局面。而寻找后手有必胜策略的局面就比较困难,只有那些所有选择都导致下一步先手必胜的局面才是后手有必胜策略的局面。

Coq & ProofWeb

在ProofWeb的主页http://prover.cs.ru.nl点击按钮 ,然后在Select a saved file to load:中选择tarski-hg.v,然后在下面的下拉框中选择Coq,点 ,就可以看到Tarski’s Fixed Point Theorem的形式化证明过程,这个证明过程可以作为Coq和ProofWeb的一个不错的demo。

Zorn’s Lemma

Suppose a partially ordered set has the property that every chain (i.e. totally ordered subset) has an upper bound. Then the set contains at least one maximal element.
如果一个偏序集P中的每一个链C(即全序子集)都有上界x(x当然必须属于P),那么该偏序集P至少包含一个极大元。

Zorn’s lemma is equivalent to the well-ordering theorem and the axiom of choice, in the sense that any one of them, together with the Zermelo–Fraenkel axioms of set theory, is sufficient to prove the others.

Zorn’s lemma is equivalent (in ZF) to three main results:

    Hausdorff maximal principle
    Axiom of choice
    Well-ordering theorem

Moreover, Zorn’s lemma (or one of its equivalent forms) implies some major results in other mathematical areas. For example,

    Banach’s extension theorem which is used to prove one of the most fundamental results in functional analysis, the Hahn–Banach theorem
    Every vector space has a Hamel basis, a result from linear algebra
    Every commutative unital ring has a maximal ideal, a result from ring theory
    Tychonoff’s theorem in topology

In this sense, we see how Zorn’s lemma can be seen as a powerful tool, especially in the sense of unified mathematics.

关于无穷这个词的意义

有人说:

数学家们不可能谈论由无限符号刻画的数学系统的存在性,那是幻觉:)由有限个符号(哪怕它包含无限符号)刻画的系统仍然是有限的。

问题在于语言,就出在“无限”这个名词上,假设我们换个名字,其实就会发现,它跟其他的符号没有任何区别。我们误以为包含“无限”这个符号的语言所描绘的那个假设的存在是无限的,但实际上根本不是。

我猜想,无限应该是人脑对一些序列进行归纳的产物。所谓实无穷潜无穷之争,无非是这个无穷符号的运算规则之争,如果扯到假设的那个无限存在之争,就永远扯不清了。

持这种观点的人显然没有弄清楚无穷这个术语的含义是怎么规定出来的。只要规定:『0是自然数,任何自然数的后继是自然数,0不是任何自然数的后继,任何两个不同自然数的后继也不同』那么任何满足这四条规定(连归纳公理都用不着)的集合的元素就一定无法一一映射到任何有限个元素的集合上,而任何有限集合却能够一一映射到该集合的某个子集上。这种性质当然可以不起名叫『无穷』,但无论如何这种性质不是任何有限集合所具有的,无论给这种性质起个什么名字,这种性质本身都是特殊的。纠缠于这种性质是否能够命名为『无穷』,纯属吃饱了撑的。

Finding all paths from source to destination

[cc lang=”cpp”]
stack node_stack;
set node_set;
AllPathFromSourceToDestination(node s, node d) {
node_stack.push(s);
node_set.add(s); //mark each node in the path
// for each node v that adjacent with node s:
for_each(node v, adjacent(v,s)) {
if(v == d) {
Output(node_stack);
} else {
if(node_set.has(v)==false) {
AllPathFromSourceToDestination(v, d);
}
}
}
node_set.del(s);
node_stack.pop(s);
}
[/cc]

Sorting network

The following is network-sorting algorithm for less than 33 elements.

What is Sorting Network? Wiki: sorting network

List of sorting networks:
From: sorting networks
Input the number n (maximum 32)
Algorithm choices: “Best”
Click [Take a look] button.

—————————
Zero-one principle

While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially when they are larger. However, because of the so-called zero-one principle, far fewer trials are in fact needed to test the validity of a sorting network.

The zero-one principle states that a sorting network is valid if it can sort all 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of the Bouricius’s Theorem in 1954 by W. G. Bouricius.

[cc lang=”cpp”]
static const unsigned int network02[][2] = {
{ 0, 1},
};
static const unsigned int network03[][2] = {
{ 1, 2},
{ 0, 2},
{ 0, 1},
};
static const unsigned int network04[][2] = {
{ 0, 1}, { 2, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network05[][2] = {
{ 0, 1}, { 3, 4},
{ 2, 4},
{ 2, 3}, { 1, 4},
{ 0, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network06[][2] = {
{ 1, 2}, { 4, 5},
{ 0, 2}, { 3, 5},
{ 0, 1}, { 3, 4}, { 2, 5},
{ 0, 3}, { 1, 4},
{ 2, 4}, { 1, 3},
{ 2, 3},
};
static const unsigned int network07[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6},
{ 0, 2}, { 3, 5}, { 4, 6},
{ 0, 1}, { 4, 5}, { 2, 6},
{ 0, 4}, { 1, 5},
{ 0, 3}, { 2, 5},
{ 1, 3}, { 2, 4},
{ 2, 3},
};
static const unsigned int network08[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7},
{ 1, 5}, { 2, 6},
{ 1, 4}, { 3, 6},
{ 2, 4}, { 3, 5},
{ 3, 4},
};
static const unsigned int network09[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7},
{ 1, 2}, { 4, 5}, { 7, 8},
{ 0, 1}, { 3, 4}, { 6, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 8},
{ 3, 6}, { 4, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 7}, { 2, 6},
{ 1, 3}, { 4, 6},
{ 2, 4}, { 5, 6},
{ 2, 3},
};
static const unsigned int network10[][2] = {
{ 4, 9}, { 3, 8}, { 2, 7}, { 1, 6}, { 0, 5},
{ 1, 4}, { 6, 9}, { 0, 3}, { 5, 8},
{ 0, 2}, { 3, 6}, { 7, 9},
{ 0, 1}, { 2, 4}, { 5, 7}, { 8, 9},
{ 1, 2}, { 4, 6}, { 7, 8}, { 3, 5},
{ 2, 5}, { 6, 8}, { 1, 3}, { 4, 7},
{ 2, 3}, { 6, 7},
{ 3, 4}, { 5, 6},
{ 4, 5},
};
static const unsigned int network11[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 1, 3}, { 5, 7}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 3, 7},
{ 1, 5}, { 6,10}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network12[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11},
{ 1, 3}, { 5, 7}, { 9,11}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 7,11},
{ 1, 5}, { 6,10}, { 3, 7}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 7,11}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network13[][2] = {
{ 1, 7}, { 9,11}, { 3, 4}, { 5, 8}, { 0,12}, { 2, 6},
{ 0, 1}, { 2, 3}, { 4, 6}, { 8,11}, { 7,12}, { 5, 9},
{ 0, 2}, { 3, 7}, {10,11}, { 1, 4}, { 6,12},
{ 7, 8}, {11,12}, { 4, 9}, { 6,10},
{ 3, 4}, { 5, 6}, { 8, 9}, {10,11}, { 1, 7},
{ 2, 6}, { 9,11}, { 1, 3}, { 4, 7}, { 8,10}, { 0, 5},
{ 2, 5}, { 6, 8}, { 9,10},
{ 1, 2}, { 3, 5}, { 7, 8}, { 4, 6},
{ 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 3, 4}, { 5, 6},
};
static const unsigned int network14[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13},
{ 5,10}, { 6, 9}, { 3,12}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network15[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network16[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11}, {13,15},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7}, {11,15},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14}, { 7,15},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network17[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {15,16},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {14,16},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {14,15}, {13,16},
{ 1, 5}, { 2, 6}, {12,15}, {11,16},
{ 1, 4}, { 3, 6}, {12,14}, {13,15}, { 7,16},
{ 2, 4}, { 3, 5}, {13,14}, {10,15},
{ 3, 4}, { 8,13}, { 9,14}, {11,15},
{ 8,12}, { 9,13}, {11,14}, { 6,15},
{ 9,12}, {10,13}, { 5,14}, { 7,15},
{10,12}, {11,13}, { 0, 9}, { 7,14},
{11,12}, { 0, 8}, { 1,10}, { 4,13},
{ 1, 9}, { 2,11}, { 3,12}, { 5,13},
{ 1, 8}, { 3,11}, { 2, 9}, { 6,13},
{ 2, 8}, { 3,10}, { 7,13}, { 6,11},
{ 3, 9}, { 5,10}, { 7,12},
{ 3, 8}, { 4, 9}, { 7,11},
{ 4, 8}, { 5, 9}, { 7,10},
{ 5, 8}, { 6, 9},
{ 6, 8}, { 7, 9},
{ 7, 8},
};
static const unsigned int network18[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17},
{ 0, 2}, { 1, 3}, { 6, 8}, { 9,11}, {10,12}, {15,17},
{ 1, 2}, { 6, 7}, { 5, 8}, {10,11}, {15,16}, {14,17},
{ 4, 7}, { 3, 8}, {13,16}, {12,17},
{ 4, 6}, { 5, 7}, {13,15}, {14,16}, { 8,17},
{ 5, 6}, { 2, 7}, {14,15}, {11,16},
{ 0, 5}, { 1, 6}, { 3, 7}, { 9,14}, {10,15}, {12,16},
{ 0, 4}, { 1, 5}, { 3, 6}, { 9,13}, {10,14}, {12,15}, { 7,16},
{ 1, 4}, { 2, 5}, {10,13}, {11,14}, { 0, 9}, { 6,15}, { 8,16},
{ 2, 4}, { 3, 5}, {11,13}, {12,14}, { 1,10}, { 7,15},
{ 3, 4}, {12,13}, { 1, 9}, { 2,11}, { 5,14}, { 8,15},
{ 3,12}, { 2, 9}, { 4,13}, { 7,14},
{ 3,11}, { 5,13}, { 8,14},
{ 3,10}, { 6,13},
{ 3, 9}, { 7,13}, { 5,10}, { 6,11},
{ 8,13}, { 4, 9}, { 7,12},
{ 5, 9}, { 8,12}, { 7,11},
{ 8,11}, { 6, 9}, { 7,10},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network19[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {12,13}, {14,15}, {17,18},
{ 0, 2}, { 1, 3}, { 6, 8}, {11,13}, {16,18},
{ 1, 2}, { 6, 7}, { 5, 8}, {11,12}, {10,13}, {16,17}, {15,18},
{ 4, 7}, { 3, 8}, { 9,12}, {14,17}, {13,18},
{ 4, 6}, { 5, 7}, { 9,11}, {10,12}, {14,16}, {15,17}, { 8,18},
{ 5, 6}, { 2, 7}, {10,11}, {15,16}, { 9,14}, {12,17},
{ 0, 5}, { 1, 6}, { 3, 7}, {10,15}, {11,16}, {13,17},
{ 0, 4}, { 1, 5}, { 3, 6}, {10,14}, {12,16}, { 7,17},
{ 1, 4}, { 2, 5}, {13,16}, {11,14}, {12,15}, { 0,10}, { 8,17},
{ 2, 4}, { 3, 5}, {13,15}, {12,14}, { 0, 9}, { 1,11}, { 6,16},
{ 3, 4}, {13,14}, { 1,10}, { 2,12}, { 5,15}, { 7,16},
{ 1, 9}, { 3,13}, { 2,10}, { 4,14}, { 8,16}, { 7,15},
{ 3,12}, { 2, 9}, { 5,14}, { 8,15},
{ 3,11}, { 6,14},
{ 3,10}, { 7,14}, { 6,11},
{ 3, 9}, { 8,14}, { 5,10}, { 7,12},
{ 4, 9}, { 8,13}, { 7,11},
{ 5, 9}, { 8,12}, { 7,10},
{ 8,11}, { 6, 9},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network20[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {15,16}, {18,19},
{ 2, 4}, { 7, 9}, {12,14}, {17,19},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {17,18}, {16,19},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {14,19},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {15,17}, {16,18}, { 9,19},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {16,17}, {10,15}, {13,18},
{ 1, 6}, { 2, 7}, { 4, 8}, {11,16}, {12,17}, {14,18}, { 0,10},
{ 1, 5}, { 3, 7}, {11,15}, {13,17}, { 8,18},
{ 4, 7}, { 2, 5}, { 3, 6}, {14,17}, {12,15}, {13,16}, { 1,11}, { 9,18},
{ 4, 6}, { 3, 5}, {14,16}, {13,15}, { 1,10}, { 2,12}, { 7,17},
{ 4, 5}, {14,15}, { 3,13}, { 2,10}, { 6,16}, { 8,17},
{ 4,14}, { 3,12}, { 5,15}, { 9,17}, { 8,16},
{ 4,13}, { 3,11}, { 6,15}, { 9,16},
{ 4,12}, { 3,10}, { 7,15},
{ 4,11}, { 8,15}, { 7,12},
{ 4,10}, { 9,15}, { 6,11}, { 8,13},
{ 5,10}, { 9,14}, { 8,12},
{ 6,10}, { 9,13}, { 8,11},
{ 9,12}, { 7,10},
{ 9,11}, { 8,10},
{ 9,10},
};
static const unsigned int network21[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {16,17}, {19,20},
{ 2, 4}, { 7, 9}, {12,14}, {15,17}, {18,20},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {15,16}, {18,19}, {17,20},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {16,19}, {14,20},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {17,19}, {16,18}, { 9,20},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {17,18}, {10,16}, {13,19},
{ 1, 6}, { 2, 7}, { 4, 8}, {10,15}, {11,17}, {12,18}, {14,19},
{ 1, 5}, { 3, 7}, {11,16}, {13,18}, { 8,19},
{ 4, 7}, { 2, 5}, { 3, 6}, {11,15}, {14,18}, {13,16}, { 9,19},
{ 4, 6}, { 3, 5}, {12,15}, {14,17}, { 0,11}, { 7,18},
{ 4, 5}, {14,16}, {13,15}, { 0,10}, { 1,12}, { 6,17}, { 8,18},
{14,15}, { 1,11}, { 2,13}, { 5,16}, { 9,18}, { 8,17},
{ 1,10}, { 3,14}, { 4,15}, { 6,16}, { 9,17},
{ 4,14}, { 3,13}, { 2,10}, { 7,16},
{ 4,13}, { 3,11}, { 8,16},
{ 4,12}, { 3,10}, { 9,16}, { 7,13}, { 8,14},
{ 4,11}, { 6,12}, { 9,15}, { 8,13},
{ 4,10}, { 5,11}, { 9,14},
{ 5,10}, { 6,11}, { 9,13},
{ 6,10}, { 8,11}, { 9,12},
{ 7,10}, { 9,11},
{ 8,10},
{ 9,10},
};
static const unsigned int network22[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21},
{ 2, 4}, { 5, 7}, { 8,10}, {13,15}, {16,18}, {19,21},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {13,14}, {12,15}, {16,17}, {19,20}, {18,21},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {16,19}, {17,20}, {15,21},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {11,13}, {12,14}, {18,20}, {17,19}, {10,21},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {12,13}, {18,19}, {11,17}, {14,20},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {11,16}, {12,18}, {13,19}, {15,20},
{ 1, 6}, { 3, 8}, {12,17}, {14,19}, { 0,11}, { 9,20},
{ 1, 5}, { 4, 8}, { 3, 6}, {12,16}, {15,19}, {14,17}, {10,20},
{ 2, 5}, { 4, 7}, {13,16}, {15,18}, { 1,12}, { 8,19},
{ 4, 6}, { 3, 5}, {15,17}, {14,16}, { 1,11}, { 2,13}, { 7,18}, { 9,19},
{ 4, 5}, {15,16}, { 3,14}, { 2,11}, { 6,17}, {10,19},
{ 4,15}, { 3,13}, { 5,16}, { 7,17}, {10,18},
{ 4,14}, { 3,12}, { 6,16}, { 9,17},
{ 4,13}, { 3,11}, { 7,16}, {10,17},
{ 4,12}, { 8,16}, { 7,13},
{ 4,11}, { 9,16}, { 6,12}, { 8,14},
{10,16}, { 5,11}, { 7,12}, { 9,15},
{ 6,11}, {10,15}, { 9,14},
{ 7,11}, {10,14}, { 9,12},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network23[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {12,13}, {15,16}, {18,19}, {21,22},
{ 2, 4}, { 5, 7}, { 8,10}, {11,13}, {14,16}, {17,19}, {20,22},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {11,12}, {14,15}, {13,16}, {17,18}, {20,21}, {19,22},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {12,15}, {17,20}, {18,21}, {16,22},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {13,15}, {12,14}, {19,21}, {18,20}, {11,17}, {10,22},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {13,14}, {19,20}, {12,18}, {15,21},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {13,19}, {12,17}, {14,20}, {16,21},
{ 1, 6}, { 3, 8}, {13,18}, {15,20}, { 0,12}, { 9,21},
{ 1, 5}, { 4, 8}, { 3, 6}, {13,17}, {16,20}, {15,18}, { 0,11}, {10,21},
{ 2, 5}, { 4, 7}, {14,17}, {16,19}, { 1,13}, { 8,20},
{ 4, 6}, { 3, 5}, {16,18}, {15,17}, { 1,12}, { 2,14}, { 7,19}, { 9,20},
{ 4, 5}, {16,17}, { 1,11}, { 3,15}, { 6,18}, {10,20},
{ 4,16}, { 3,14}, { 2,11}, { 5,17}, { 7,18}, {10,19},
{ 4,15}, { 3,12}, { 6,17}, { 9,18},
{ 4,14}, { 3,11}, { 7,17}, {10,18},
{ 4,13}, { 8,17},
{ 4,12}, { 9,17}, { 7,13}, { 8,14},
{ 4,11}, {10,17}, { 6,12}, { 9,15},
{ 5,11}, { 7,12}, {10,16}, { 9,14},
{ 6,11}, {10,15}, { 9,12},
{ 7,11}, {10,14},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network24[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {22,23},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {21,22}, {20,23},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,21}, {19,22}, {17,23},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {20,22}, {19,21}, {12,18}, {11,23},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {20,21}, {13,19}, {16,22}, { 0,12},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {14,20}, {13,18}, {15,21}, {17,22},
{ 2, 7}, { 4, 9}, {14,19}, {16,21}, { 1,13}, {10,22},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,18}, {17,21}, {16,19}, { 1,12}, {11,22},
{ 3, 6}, { 5, 8}, {15,18}, {17,20}, { 2,14}, { 9,21},
{ 5, 7}, { 4, 6}, {17,19}, {16,18}, { 2,13}, { 3,15}, { 8,20}, {10,21},
{ 5, 6}, {17,18}, { 2,12}, { 4,16}, { 7,19}, {11,21},
{ 5,17}, { 4,15}, { 3,12}, { 6,18}, { 8,19}, {11,20},
{ 5,16}, { 4,13}, { 7,18}, {10,19},
{ 5,15}, { 4,12}, { 8,18}, {11,19},
{ 5,14}, { 9,18},
{ 5,13}, {10,18}, { 8,14}, { 9,15},
{ 5,12}, {11,18}, { 7,13}, {10,16},
{ 6,12}, { 8,13}, {11,17}, {10,15},
{ 7,12}, {11,16}, {10,13},
{ 8,12}, {11,15},
{ 9,12}, {11,14},
{11,13}, {10,12},
{11,12},
};
static const unsigned int network25[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {21,22}, {23,24},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23}, {22,24},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {22,23}, {20,24},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,22}, {19,23}, {17,24},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {18,21}, {20,23}, {11,24},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {19,21}, {20,22}, {16,23},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {20,21}, {12,19}, {15,22}, {17,23},
{ 2, 7}, { 4, 9}, {12,18}, {13,20}, {14,21}, {16,22}, {10,23},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,20}, {13,18}, {17,22}, {11,23},
{ 3, 6}, { 5, 8}, {14,19}, {16,20}, {17,21}, { 0,13}, { 9,22},
{ 5, 7}, { 4, 6}, {14,18}, {15,19}, {17,20}, { 0,12}, { 8,21}, {10,22},
{ 5, 6}, {15,18}, {17,19}, { 1,14}, { 7,20}, {11,22},
{16,18}, { 2,15}, { 1,12}, { 6,19}, { 8,20}, {11,21},
{17,18}, { 2,14}, { 3,16}, { 7,19}, {10,20},
{ 2,13}, { 4,17}, { 5,18}, { 8,19}, {11,20},
{ 2,12}, { 5,17}, { 4,16}, { 3,13}, { 9,19},
{ 5,16}, { 3,12}, { 4,14}, {10,19},
{ 5,15}, { 4,12}, {11,19}, { 9,16}, {10,17},
{ 5,14}, { 8,15}, {11,18}, {10,16},
{ 5,13}, { 7,14}, {11,17},
{ 5,12}, { 6,13}, { 8,14}, {11,16},
{ 6,12}, { 8,13}, {10,14}, {11,15},
{ 7,12}, { 9,13}, {11,14},
{ 8,12}, {11,13},
{ 9,12},
{10,12},
{11,12},
};
static const unsigned int network26[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21}, {22,23}, {24,25},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {19,21}, {22,24}, {23,25},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {16,17}, {15,18}, {19,20}, {23,24}, {21,25},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,16}, {14,17}, {19,23}, {20,24}, {18,25},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {15,17}, {14,16}, {19,22}, {21,24}, {12,25},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {15,16}, {20,22}, {21,23}, {17,24},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {21,22}, {13,20}, {16,23}, {18,24},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {13,19}, {14,21}, {15,22}, {17,23}, {11,24},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {14,19}, {18,23}, { 0,13}, {12,24},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {17,21}, {18,22}, { 1,14}, {10,23},
{ 2, 6}, { 3, 7}, { 5, 8}, {15,19}, {16,20}, {18,21}, { 1,13}, { 9,22}, {12,23},
{ 3, 6}, { 5, 7}, {16,19}, {18,20}, { 2,15}, { 8,21}, {10,22},
{ 4, 6}, {17,19}, { 2,14}, { 3,16}, { 7,20}, {11,22},
{ 5, 6}, {18,19}, { 2,13}, { 4,17}, { 8,20}, {12,22}, {11,21},
{ 5,18}, { 4,16}, { 3,13}, { 6,19}, {10,20}, {12,21},
{ 5,17}, { 4,14}, { 7,19}, {12,20},
{ 5,16}, { 4,13}, { 8,19},
{ 5,15}, { 9,19},
{ 5,14}, {10,19}, { 8,15}, { 9,16},
{ 5,13}, {11,19}, { 7,14}, {10,17},
{12,19}, { 6,13}, { 8,14}, {10,16}, {11,18},
{ 7,13}, {12,18}, {11,16}, {10,14},
{ 8,13}, {12,17}, {11,15},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network27[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {16,17}, {18,19}, {21,22}, {23,24}, {25,26},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {17,19}, {20,22}, {23,25}, {24,26},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {17,18}, {15,19}, {20,21}, {24,25}, {22,26},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,17}, {14,18}, {20,24}, {21,25}, {19,26},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {13,16}, {15,18}, {20,23}, {22,25}, {12,26},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {14,16}, {15,17}, {21,23}, {22,24}, {13,20}, {18,25},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {15,16}, {22,23}, {14,21}, {17,24}, {19,25},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {15,22}, {14,20}, {16,23}, {19,24}, {11,25},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {17,23}, { 0,14}, {12,25},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {18,23}, {17,21}, { 0,13}, {10,24},
{ 2, 6}, { 3, 7}, { 5, 8}, {19,23}, {16,20}, {18,22}, { 1,15}, {12,24},
{ 3, 6}, { 5, 7}, {17,20}, {19,22}, { 2,16}, { 1,13}, { 9,23},
{ 4, 6}, {18,20}, {19,21}, { 2,15}, { 3,17}, { 8,22}, {10,23},
{ 5, 6}, {19,20}, { 2,14}, { 4,18}, { 7,21}, {11,23},
{ 2,13}, { 5,19}, { 4,17}, { 3,14}, { 6,20}, { 8,21}, {12,23}, {11,22},
{ 5,18}, { 3,13}, { 4,15}, { 7,20}, {10,21}, {12,22},
{ 5,17}, { 4,13}, { 8,20}, {12,21},
{ 5,16}, { 9,20},
{ 5,15}, {10,20}, { 9,16},
{ 5,14}, {11,20}, { 8,15}, {10,17},
{ 5,13}, {12,20}, { 7,14}, {10,16}, {11,18},
{ 6,13}, { 8,14}, {12,19}, {11,16},
{ 7,13}, {12,18}, {10,14}, {11,15},
{ 8,13}, {12,17},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network28[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {22,23}, {24,25}, {26,27},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {24,26}, {25,27},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {21,22}, {25,26}, {23,27},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {21,25}, {22,26}, {20,27},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {21,24}, {23,26}, {13,27},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {22,24}, {23,25}, {14,21}, {19,26},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {23,24}, {15,22}, {18,25}, {20,26}, { 0,14},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,23}, {15,21}, {17,24}, {20,25}, {12,26},
{ 2, 8}, { 4,10}, {16,22}, {18,24}, { 1,15}, {11,25}, {13,26},
{ 2, 7}, { 5,10}, { 4, 8}, {16,21}, {19,24}, {18,22}, { 1,14}, {13,25},
{ 6,10}, { 3, 7}, { 5, 9}, {20,24}, {17,21}, {19,23}, { 2,16},
{ 4, 7}, { 6, 9}, {18,21}, {20,23}, { 2,15}, { 3,17}, {10,24},
{ 5, 7}, { 6, 8}, {19,21}, {20,22}, { 2,14}, { 4,18}, { 9,23}, {11,24},
{ 6, 7}, {20,21}, { 4,17}, { 5,19}, { 3,14}, { 8,22}, {12,24},
{ 6,20}, { 5,17}, { 4,15}, { 7,21}, { 9,22}, {13,24}, {12,23},
{ 6,19}, { 4,14}, { 5,16}, { 8,21}, {11,22}, {13,23},
{ 6,18}, { 5,14}, { 9,21}, {13,22},
{ 6,17}, {10,21},
{ 6,16}, {11,21}, {10,17},
{ 6,15}, {12,21}, { 9,16}, {11,18},
{ 6,14}, {13,21}, { 8,15}, {11,17}, {12,19},
{ 7,14}, { 9,15}, {13,20}, {12,17},
{ 8,14}, {13,19}, {11,15}, {12,16},
{ 9,14}, {13,18},
{13,17}, {10,14},
{11,14}, {13,16},
{12,14}, {13,15},
{13,14},
};
static const unsigned int network29[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {22,24}, {25,27}, {26,28},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {22,23}, {26,27}, {21,25}, {24,28},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {22,26}, {23,27}, {20,28},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {22,25}, {24,27}, {13,28},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {23,25}, {24,26}, {14,22}, {19,27},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {24,25}, {14,21}, {15,23}, {18,26}, {20,27},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,24}, {15,21}, {17,25}, {20,26}, {12,27},
{ 2, 8}, { 4,10}, {16,23}, {18,25}, { 0,15}, {11,26}, {13,27},
{ 2, 7}, { 5,10}, { 4, 8}, {16,22}, {19,25}, { 0,14}, {13,26},
{ 6,10}, { 3, 7}, { 5, 9}, {16,21}, {20,25}, {18,22}, {19,23},
{ 4, 7}, { 6, 9}, {17,21}, {20,24}, { 1,16}, {10,25},
{ 5, 7}, { 6, 8}, {18,21}, {20,23}, { 2,17}, { 1,14}, { 9,24}, {11,25},
{ 6, 7}, {19,21}, {20,22}, { 2,16}, { 3,18}, { 8,23}, {12,25},
{20,21}, { 2,15}, { 4,19}, { 7,22}, { 9,23}, {13,25}, {12,24},
{ 2,14}, { 4,18}, { 5,20}, { 6,21}, { 8,22}, {11,23}, {13,24},
{ 6,20}, { 5,18}, { 3,14}, { 4,15}, { 9,22}, {13,23},
{ 6,19}, { 4,14}, { 5,16}, {10,22},
{ 6,18}, { 5,14}, {11,22},
{ 6,17}, {12,22}, {10,18}, {11,19},
{ 6,16}, {13,22}, { 9,17}, {11,18}, {12,20},
{ 6,15}, { 8,16}, {13,21}, {12,18},
{ 6,14}, { 7,15}, { 9,16}, {13,20},
{ 7,14}, { 9,15}, {13,19}, {12,16},
{ 8,14}, {13,18}, {11,15},
{ 9,14}, {13,17},
{10,14}, {13,16},
{11,14}, {13,15},
{12,14},
{13,14},
};
static const unsigned int network30[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {18,20}, {19,21}, {22,24}, {23,25}, {26,28}, {27,29},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {15,16}, {19,20}, {17,21}, {23,24}, {27,28}, {22,26}, {25,29},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {15,19}, {16,20}, {23,27}, {24,28}, {21,29},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {15,18}, {17,20}, {23,26}, {25,28}, {14,29},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {16,18}, {17,19}, {24,26}, {25,27}, {15,23}, {20,28},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {17,18}, {25,26}, {15,22}, {16,24}, {19,27}, {21,28},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {17,25}, {16,22}, {18,26}, {21,27}, { 0,15}, {13,28},
{ 2, 9}, { 4,11}, {17,24}, {19,26}, { 1,16}, {12,27}, {14,28},
{ 2, 8}, { 5,11}, {17,23}, {20,26}, { 1,15}, {14,27},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {17,22}, {21,26}, {19,23}, {20,24},
{ 3, 7}, { 6,10}, {18,22}, {21,25}, { 2,17}, {11,26},
{ 4, 7}, { 6, 9}, {19,22}, {21,24}, { 2,16}, { 3,18}, {10,25}, {12,26},
{ 5, 7}, { 6, 8}, {20,22}, {21,23}, { 2,15}, { 4,19}, { 9,24}, {13,26},
{ 6, 7}, {21,22}, { 4,18}, { 5,20}, { 3,15}, { 8,23}, {10,24}, {14,26},
{ 6,21}, { 5,18}, { 4,16}, { 7,22}, {10,23}, {13,24}, {14,25},
{ 6,20}, { 4,15}, { 5,17}, { 8,22}, {12,23}, {14,24},
{ 6,19}, { 5,15}, { 9,22}, {14,23},
{ 6,18}, {10,22},
{ 6,17}, {11,22}, {10,18},
{ 6,16}, {12,22}, { 9,17}, {11,19},
{ 6,15}, {13,22}, { 8,16}, {10,17}, {12,20},
{14,22}, { 7,15}, {10,16}, {12,19}, {13,21},
{ 8,15}, {14,21}, {13,19}, {12,16},
{ 9,15}, {14,20}, {13,17},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network31[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28}, {29,30},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {16,18}, {19,21}, {20,22}, {23,25}, {24,26}, {27,29}, {28,30},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {16,17}, {20,21}, {15,19}, {18,22}, {24,25}, {28,29}, {23,27}, {26,30},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {16,20}, {17,21}, {24,28}, {25,29}, {15,23}, {22,30},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {16,19}, {18,21}, {24,27}, {26,29}, {14,30},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {17,19}, {18,20}, {25,27}, {26,28}, {16,24}, {21,29},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {18,19}, {26,27}, {16,23}, {17,25}, {20,28}, {22,29},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {18,26}, {17,23}, {19,27}, {22,28}, { 0,16}, {13,29},
{ 2, 9}, { 4,11}, {18,25}, {20,27}, { 0,15}, { 1,17}, {12,28}, {14,29},
{ 2, 8}, { 5,11}, {18,24}, {21,27}, { 1,15}, {14,28},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {18,23}, {22,27}, {20,24}, {21,25},
{ 3, 7}, { 6,10}, {19,23}, {22,26}, { 2,18}, {11,27},
{ 4, 7}, { 6, 9}, {20,23}, {22,25}, { 2,17}, { 3,19}, {10,26}, {12,27},
{ 5, 7}, { 6, 8}, {21,23}, {22,24}, { 2,16}, { 4,20}, { 9,25}, {13,27},
{ 6, 7}, {22,23}, { 2,15}, { 4,19}, { 5,21}, { 8,24}, {10,25}, {14,27},
{ 6,22}, { 5,19}, { 3,15}, { 4,16}, { 7,23}, {10,24}, {13,25}, {14,26},
{ 6,21}, { 4,15}, { 5,17}, { 8,23}, {12,24}, {14,25},
{ 6,20}, { 5,15}, { 9,23}, {14,24},
{ 6,19}, {10,23},
{ 6,18}, {11,23},
{ 6,17}, {12,23}, {10,18}, {11,19},
{ 6,16}, {13,23}, { 9,17}, {12,20},
{ 6,15}, {14,23}, { 8,16}, {10,17}, {12,19}, {13,21},
{ 7,15}, {10,16}, {14,22}, {13,19},
{ 8,15}, {14,21}, {12,16}, {13,17},
{ 9,15}, {14,20},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network32[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29}, {30,31},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {12,14}, {13,15}, {16,18}, {17,19}, {20,22}, {21,23}, {24,26}, {25,27}, {28,30}, {29,31},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {13,14}, { 8,12}, {11,15}, {17,18}, {21,22}, {16,20}, {19,23}, {25,26}, {29,30}, {24,28}, {27,31},
{ 1, 5}, { 2, 6}, { 9,13}, {10,14}, { 0, 8}, { 7,15}, {17,21}, {18,22}, {25,29}, {26,30}, {16,24}, {23,31},
{ 1, 4}, { 3, 6}, { 9,12}, {11,14}, {17,20}, {19,22}, {25,28}, {27,30}, { 0,16}, {15,31},
{ 2, 4}, { 3, 5}, {10,12}, {11,13}, { 1, 9}, { 6,14}, {18,20}, {19,21}, {26,28}, {27,29}, {17,25}, {22,30},
{ 3, 4}, {11,12}, { 1, 8}, { 2,10}, { 5,13}, { 7,14}, {19,20}, {27,28}, {17,24}, {18,26}, {21,29}, {23,30},
{ 3,11}, { 2, 8}, { 4,12}, { 7,13}, {19,27}, {18,24}, {20,28}, {23,29}, { 1,17}, {14,30},
{ 3,10}, { 5,12}, {19,26}, {21,28}, { 1,16}, { 2,18}, {13,29}, {15,30},
{ 3, 9}, { 6,12}, {19,25}, {22,28}, { 2,16}, {15,29},
{ 3, 8}, { 7,12}, { 5, 9}, { 6,10}, {19,24}, {23,28}, {21,25}, {22,26},
{ 4, 8}, { 7,11}, {20,24}, {23,27}, { 3,19}, {12,28},
{ 5, 8}, { 7,10}, {21,24}, {23,26}, { 3,18}, { 4,20}, {11,27}, {13,28},
{ 6, 8}, { 7, 9}, {22,24}, {23,25}, { 3,17}, { 5,21}, {10,26}, {14,28},
{ 7, 8}, {23,24}, { 3,16}, { 5,20}, { 6,22}, { 9,25}, {11,26}, {15,28},
{ 7,23}, { 6,20}, { 4,16}, { 5,17}, { 8,24}, {11,25}, {14,26}, {15,27},
{ 7,22}, { 5,16}, { 6,18}, { 9,24}, {13,25}, {15,26},
{ 7,21}, { 6,16}, {10,24}, {15,25},
{ 7,20}, {11,24},
{ 7,19}, {12,24},
{ 7,18}, {13,24}, {11,19}, {12,20},
{ 7,17}, {14,24}, {10,18}, {13,21},
{ 7,16}, {15,24}, { 9,17}, {11,18}, {13,20}, {14,22},
{ 8,16}, {11,17}, {15,23}, {14,20},
{ 9,16}, {15,22}, {13,17}, {14,18},
{10,16}, {15,21},
{11,16}, {15,20},
{12,16}, {15,19},
{13,16}, {15,18},
{14,16}, {15,17},
{15,16},
};

typedef struct {
const unsigned int comparators;
const unsigned int (*pNetwork)[2];
} Network;

#define elemof(ary) (sizeof(ary)/sizeof(ary[0]))
#define NETWORK(n) {elemof(network##n), network##n}

static const Network networks[] = {
{0, NULL},
{0, NULL},
NETWORK(02),
NETWORK(03),
NETWORK(04),
NETWORK(05),
NETWORK(06),
NETWORK(07),
NETWORK(08),
NETWORK(09),
NETWORK(10),
NETWORK(11),
NETWORK(12),
NETWORK(13),
NETWORK(14),
NETWORK(15),
NETWORK(16),
NETWORK(17),
NETWORK(18),
NETWORK(19),
NETWORK(20),
NETWORK(21),
NETWORK(22),
NETWORK(23),
NETWORK(24),
NETWORK(25),
NETWORK(26),
NETWORK(27),
NETWORK(28),
NETWORK(29),
NETWORK(30),
NETWORK(31),
NETWORK(32),
};
#undef NETWORK

static const size_t cutoff = elemof(networks);

template
inline void networkSort(Elem *p, size_t n) {
const unsigned int (* pNetwork)[2], (* pEnd)[2];
Elem *p0, *p1;
assert(n < elemof(networks)); pNetwork = networks[n].pNetwork; pEnd = pNetwork + networks[n].comparators; for(; pNetwork < pEnd; pNetwork++) { p0 = p + (*pNetwork)[0]; p1 = p + (*pNetwork)[1]; if(*p1 < *p0) swap(p0, p1); } } [/cc]

号称世界上最难的逻辑题

已知:
1.神无所不知只说真话,鬼无所不知只说假话,人有所不知胡乱说话,除此之外三者没有任何区别。他们一定回答且只能回答任何有确定答案的是非题。
2.“Da”和“Ja”一个永远代表“是”另一个永远代表“否”,但你完全不知道二者分别代表哪个。

问题Z:你面前站着神、鬼、人各一,你不知道三者分别是谁,你必须通过提问正确区分出三者。你每次只能对其中一个提问,一共只能问三次,但你每次提问得到的回答只能是“Da”或“Ja”。

如果你觉得Z太难,这里有一个简化版Z’:跟Z类似,但得到的答案只能是“是”或“否”。

如果你还是觉得太难,还有一个更简单的问题Y:你面前有两条路,一条通向天堂,一条通向地狱。路口站着神、鬼各一,你不知道二者分别是谁。你现在只能对其中一个提出一个是非题,判断出哪条路通向天堂。但你提问得到的回答只会是“Da”或“Ja”。

如果你觉得Y也太难,也可以简化为Y’:跟Y类似,但得到的答案只会是“是”或“否”。

附加条件:
如果你解决了Z或Z’,那么请加一个条件:你对其中一个问的问题中不允许同时提及另外两个。
如果你解决了Y或Y’,那么请加一个条件:你对其中一个问的问题中不允许提及另外一个。

问题Y还可以有如下变体Y”:路口只站着一个家伙,你只知道他要么是神要么是鬼。你现在只能向他问一个是非题,判断出哪条路通向天堂。其他不变。

一点提示:
对A提问:『将鬼、人、神分别编号为1,2,3,那么请问B的编号大于C么?』
对A提问:『如果我问你『B是乱说话的人么?』,你会回答什么?』
对任何一个提问:请问『……』这个问题的答案是Da么?

Next Page »