∀P: P(0) ∧ (∀x: P(x) → P(Sx)) → (∀n: P(n))
这里的P是任何一个类的陈述,它在每一个数要么真要么假。数的任何一个类,都对应了一个陈述,对于类里面的数它为真,对于类外面的数它为假。
好奇宝宝:
OK...那是如何去除掉无穷链的呢?
解答者:
因为,从理论上说,无论是否存在一个一阶公式能把它们挑选出来,仍然存在一个包含、且仅包含了标准数{0, 1, 2, ...}的类。如果你把类当作一个陈述P,那么P在0是真的——那就是说,0是标准数中。如果200是一个标准数则201也是等等;如果P在x是真的,也在x 1是真的。另一方面,如果你把‘仅在在标准数’这个类当作一个陈述,它在 -2*, -1*, 0*等等都是假的——那些数不在这个理论上的类中。所以‘如果它在0*为真则它在1*为真’就是为真了,因为在0*它不为真。于是我们以下图来终结:
所以这个二阶公理……
∀P: P0 ∧ (∀x: Px → P(Sx)) → (∀n: Pn)
……一下子就去除掉了任何不链接的链、有限圈,即任何非标准数。
好奇宝宝:
不过那条公理的准确意思是?我的意思是,暂时放弃短语‘标准自然数’,假定我对那些没有任何的理解,仅仅给我解释一下那条公理事实上说了什么。
解答者:
它表达了这个意思:正在讨论的模型——符合这个公理的模型——让形成这样的类是不可能的:在后继这个操作之下是封闭,包含了0但是不包含每一个东西。在这个论域中的类不可能是这样的:0在这个类中,这个类中的每一个东西的后继也在这个类中,然而它并不含有每一个东西。所以,你不能含有一个不连通的无穷的链——(如果存在的话)那将至少存在一个类,它含有了0以及所有的后继——后裔,然而并不包含那个链;而且我们有一个有启发性的新公理述说了那个不可能的。
好奇宝宝:
也许你能够使用一个更加直观的方式来说明?好比说,如果这就是我所信仰的关于这个宇宙的事情,那么,什么是我可以期望得到的呢?
解答者:
如果这就是你所信仰的你生在其中的数学模型...那么你相信了,不管是你还是其他对手,抑或是一个超级智能体,或者上帝,都不能对对象以这种方式来说‘是’或‘非’:当你给他们0,他们说‘是’;当你给他们任何他们说‘是’的对象,他们也对这个对象的后继说‘是’;然后,存在某个对象,他们说‘非’。你相信这绝不能发生,无论以什么方式。宇宙中的对象被后继安装的这种方式,从不允许那种事情发生。
好奇宝宝:
啊。如果他们对42说‘非’,我将回退并且询问41,然后是40,然后当我到了0,我将会发现他们对0说‘非’或者‘他们对41说了非,然而对40说了是’。如果我相信带有无穷公理模式的一阶逻辑,我能够期望得到什么呢?
解答者:
在那种情况,你相信不存在像那样起作用的灵巧规定的、紧凑描述的规则。不过如果你相信那个二阶版本,你相信,没有人可能像那样行动,即使他们是在随机地回答问题,或者把这个宇宙叉开一个分支来在不同的宇宙中以不同方式来回答等等。顺便注记一下,如果我们有一个有限的论域[译注2],也就是说,我们去掉了那个每一个数都有一个后继的规则,作为替代假定256是唯一没有后继的数——那么我们就可以在有限时间之内来验证这条公理了。
好奇宝宝:
我明白了。是否存在一个方法使用一阶逻辑去除掉无穷链呢?我将发现那更容易处理一点,即使它刚开始看起来更复杂。
解答者:
恐怕是没有的。一种我喜欢看待的方式是:从局部看模型如何这样的约束,一阶逻辑能够做到,然而只有二阶逻辑才能谈论链、类、作为一个整体的模型这些的性质。任何一个数是否具有后继是一个局部性质——模型从一个数的视角去看是怎样的,这样的问题。一个数加三是否等于它自己,是一个这样的问题:你能够从任何一个数它自己的位置去评估。一个数是否是偶数,这个问题你可以通过寻找唯一的一个数x使得x x等于那个数来回答。但是,当你试图说仅存在唯一的链它从0开始,借助于连通、链的想法,你在试图描述非局部的性质,这需要指定一个关于可能的类的逻辑。
好奇宝宝:
嗯。不过如果所有的局部性质都是一样的,为什么要担心整体性质呢?在一阶逻辑中,任何‘局部’公式它在0以及所有‘自然的’后继都是是真的,在所有的不连通的链它将必须为真... 对吗?亦或我弄错了什么?0-链之外的所有链——所有‘非标准数’——将像‘自然’数一样拥有同样的性质,对吗?
解答者:
恐怕不是的。算术的一阶公理不能成功地确定一个图灵机会停止——是否存在一个时刻使得一个图灵机停止。在标准数中,从我们的视角说某个图灵机‘真的不’停机——它在第0个时钟滴答不停机,在第1个时钟滴答不停机,在第2个时钟滴答不停机,以及0-链上的所有标准后继。在整数的非标准模型——拥有其它无穷链的模型——在一个非标准链中也许存在一个位置,图灵机走到那里就停止了,而且永远停止在哪里。
在这个新的模型——与一阶公理完全兼容,并且不能被它们去除掉——‘对于任一个数t这个图灵机是运行的,在t 1它仍然运行’不是真的。虽然我们可以把我们的注意力限制在‘自然’数上,我们可以发现这个图灵机在0,1,2以及0-链的后继每一个时刻都是运行的。
好奇宝宝:
OK... 我不是清楚那样做会有什么后果?
解答者:
它意味着很多事实上在标准时间上从来不停机的图灵机,仅仅使用一阶推理,是不能证明不停机的,因为它们的不停机性事实上是不能从一阶公理推论出的。逻辑是关于那些从前提导出的结论的,还记得吗?这意味着你将不能证明——不应该证明——这个图灵机停止,只使用一阶逻辑的话。
好奇宝宝:
怎么证明不成立呢?我的意思是,那些证明在哪里走不通呢?
解答者:
你将无法得到归纳中的第二步,‘对于任一个时刻t图灵机正在运行,在t 1时刻它仍将运行’。存在带有非标准数t的非标准模型否定了这个前提条件——在一个非标准时间 图灵机从运行状态停止了。我们可以把注意力仅限制在标准数的话,我们会发现那个图灵机在0,1,2等等在运行。
、
好奇宝宝:
不过如果一个图灵机事实上真的停止了,那就存在某个它停止的时刻,比如在第97步。
解答者:
是的。不过97存在于算术的所有的非标准模型,所以我们可以在一阶逻辑中证明其存在性。0是一个数,每一个数有一个后继,数不循环等等,那将存在97。每一个非标准模型至少含有标准数。所以当一个图灵机确实停机的时候,你可以在一阶算术中证明它停机——它推导出自那些前提。那正是你所期待的,假定你可以观察那个图灵机97步的话。当某图灵机事实上停机的时候你应该可以证明它停止而不需要担心无限的未来时间!当它在标准数中事实上不停机的时候——由于‘非标准停机时间’的存在,它就变成了一个问题。于是,图灵机永远运行这个结论也许事实上不能从一阶算术推导出来,因为你可以遵从一阶算术的所有的前提,然而仍有在非标准模型中的某个位置图灵机会停机。
好奇宝宝:
所以二阶算数比一阶算术更加强大,就哪些可以从前提推导出来来说?
解答者:
能够谈论较少可能的模型这个能力必然得出那一点。正像已经写到的,“关于某个苹果是真的事情对于另一个苹果不一定是真的;所以,关于单个苹果可说的东西多于关于这个世界上所有的苹果可以说的东西。”如果你能够把你的论域限制到一个更狭窄的模型的类上,那就存在更多的可以必然推导出的事实,因为你谈论的模型越大,关于它们都真的事实越少。另外二阶算数比一阶算术证明了更多的定理,它也确实是真的——比如,它能够证明一个能计算古德斯坦序列的图灵机总是到达0并停机,赫拉克勒斯总是赢得九头蛇游戏。不过呢,如果这样就一般地来说二阶逻辑是否事实上比一阶逻辑更加强大,会遇到一点争议。
好奇宝宝:
好吧。毕竟,仅仅因为没有人曾经发明一个一阶公式来去除掉所有的非标准数,并不意味着它永远不可能。未来一些聪明的数学家也许可以找到一个方式使得,对于任一个数x,使用加法、乘法、关于其它单个的数是否存在这些来对它仅作局部的事情,这个方法可以告诉我们那个数是在0-链上,亦或在某个双向无穷的链上。它将简单得就像:
(a=b*c)
解答者:
不。那不会发生。
好奇宝宝:
不过,也许,你能否找到一些完全不同的创新的方式,只用一阶公理得到全部都是标准自然数的模型。
解答者:
不可能。
好奇宝宝:
嗯...你是如何准确地知道那一点的?我的意思是,当你参加一个比赛,作为比赛选手的一条原则就是当某事看起来不可能的时候,你不要放弃。我不能明白如何使用一阶公式来检查无穷的链。不过,先前我不能认为你可以去除有限圈,一旦你讲解了,它就显得非常简单。毕竟,关于‘不可能’这个词存在两种不同的用法,一种直接用已有知识表明了某事不能实现,也就是说哪怕你是一个超级智能体,也不可能找一种做法来达成这个目标。这种情况,你需要利用已知知识给出一个确定、完整的结果,从而你可以否定每一个可能的成功途径。还有另外一种,‘不可能’一词更加通常的用法:你思考了五秒钟没有发现实现它的方法,然后就说”不可能“。一般在对知识了解有限,那个问题又看起来有些神秘主义倾向会这样。
解答者:
是的。使用一阶公式来去除掉双向无穷链,是第一种类型的不可能。我们知道它永远不可能实现。
好奇宝宝:
嗯,我知道。好吧,你有什么观点,如何说明你的观点?能用你明确的知识正面回答为什么‘不可能’吗?别用这种神秘兮兮的方式强行灌输?
解答者:
下一次,下一次我们再来好好讲讲。
译者注:
[1]非直谓的(impredicative)
[2]原文universe既可以翻译为宇宙,也可以在某些情况下翻译为“论域”。有些情况下,难以抉择,或者本身就是双关。请读者自己记住这一点。
关注 哆嗒数学网 每天获得更多数学趣文