知识源于沉淀 原作者:Eliezer Yudkowsky，人工智能专家。
译者，冯武明，多多数学网翻译团队成员。
校对:Math001
关注多多数学网，每天获取更多有趣的数学文章。
答案:
哦！你好！又回来了？
好奇宝宝:
是的，我有一个新问题。之前你说要用二阶逻辑定义自然数。不过我很确定我听说过一个叫“一阶钢琴算术”的东西，据说是定义自然数的。从名字上看，它不应该包含任何“二阶”公理。坦白说，我觉得我对这个二阶的东西没什么感觉。
答案:
好吧，让我们从下面的模型开始:
这个模型对于标准自然数有三个我们想要满足的性质:“每个数都有后继”，“如果两个数有相同的后继，则相等”，“0是唯一不是其他数的后继的数。”。在这个模型中，所有这些陈述都是真的，所以在这个意义上，它真的类似于一个自然数。
很明显，这个模型不是我们要找的自然数，因为它有一些多余的神秘数字，比如c，2*。类似c的东西甚至是圆，我当然不希望任何自然数是这样的。而且，还有一条无尽的链条，无法折叠成别的东西。
没错，这就是一阶逻辑和二阶逻辑的区别:在一阶逻辑中，我们可以去掉那些ABC——做一个陈述句，可以排除任何有那样循环的模型。但是我们无法摆脱下面的无尽链条。在二阶逻辑中，我们可以去掉多余的链条。
好奇宝宝:
你能解释一下你刚才说的吗，虽然我还不知道什么是二阶逻辑？
答案:
给我一点时间。首先，考虑下面的公式来检验“两个性质”:
x + 2 = x * 2
好奇宝宝:
换句话说，当x等于2时，这个公式为真，其他地方为假，所以它单挑出了2？
答案:
没错。以下是检查奇数的公式:
∃y: x=(2*y)+1
好奇宝宝:
好吧。这个公式说，“有一个y，所以x等于2乘以y加1”。当x为1时为真，因为0是一个数，1=(2*0)+1。当x为9时，为真，因为有一个数字4，使得(2*4)+1…正确。只要X取奇数，公式就成立，只有X取奇数才成立。
答案:
没错。现在，假设我们有一种方法来检查模型中ABC循环的存在——公式在ABC循环中为真，而在其他地方为假。然后，我可以对这个公式进行变换，得到它的否定形式，即“不允许有这样的东西存在”，再加上它，使之与“每一个数都有后继者”一起成为自然数的公理
好奇宝宝:
那么，我可以通过表示x: (x = a)来去掉ABC循环吗？
答案:
好吧，你只能说，如果你已经先告诉我A是什么，在一个去除了所有有循环的模型的逻辑中，你不能指定一个不存在的特定对象。
好奇宝宝
我明白了。好…所以移除后续圆圈的想法是…嗯。在数字0、1、2和3中，0不是任何数字的后继者。如果我有一组从1开始的数字，比如{1，2，3…}，在这个组中，1不是任何数的后继。在A，B，C中，数A是数C的后继数，数C是数B的后继数，数B是数A的后继数，如果我说“不存在一组数G，使得对于G中的任意一个数X，它是G中另一个数Y的后继数。”
答案:
啊！非常聪明。然而，你只是在使用二阶逻辑，因为你谈论的是实体的组或类，而一阶逻辑只谈论单个实体。假设我们有一个逻辑来谈小猫，谈小猫是否讨人厌。这是一个恰好包含三个不同宇宙的烦人小猫的模型:
好奇宝宝:
那么，那些“属性”(图中的“propery”)是什么呢？
答案:
他们都是可能的小猫类。它们被称为属性，因为每一类小猫都对应着该类小猫拥有而其他类小猫没有的属性。比如右上角只包含灰色小猫的类，对应的是灰色小猫为真，其他地方为假的语句，还对应一个只有灰色小猫才有，其他小猫没有的属性。事实上，从现在开始，我们认为一个“属性”只表示一个“类”
好奇宝宝:
好吧，我理解“小猫的班级”这个概念。
答案:
在一阶逻辑中，我们可以谈论单只猫，它与其他单只猫的关系，以及一只具有特殊关系的猫是否存在。在二阶逻辑中，我们可以讨论猫类以及某些类是否存在。所以，在一阶逻辑中，我可以说“有一只讨厌的猫”或者“对任何一只猫来说，它都不讨厌”或者“对任何一只猫来说，有另一只猫喜欢第一只猫”。但是，要形成一个关于“猫类”的叙述句，比如“没有猫类，以至于这个类里的每一只猫都被这个类里的另一只猫喜欢”需要二阶逻辑
好奇宝宝:
我明白了。所以，当我想说你不能有任何数量的群，以至于这个群中的任何一个数都是这个群中某个其他数的后继数。…
答案:
…..你定量的描述了对数类的存在，说明你用的是二阶逻辑。然而，在这种情况下，仅使用一阶逻辑来移除ABC循环是容易且可能的。检查此公式:
x=SSSx
好奇宝宝:
x加3等于自身？
答案:
没错。这是一个一阶公式，因为它没有讲类。在0，1，2，3…这个公式是错误的，但在A，B，C处是正确的。
好奇宝宝:
图中的加号“+”是什么意思？
答案:
好吧，我试着用加号“+”来表示“这个公式为真”，同样，假设“”表示公式为假。一个共同的想法是，我们现在有一个公式来检查3-循环，并区分它们与标准数字，如0，1和2。
好奇宝宝:
我明白了。因此，通过添加X: X = SSSX作为新的公理，我们可以去除所有包含A，B，C或任何其他非标准数的3圈模型。
答案:
是
好奇宝宝:
但是，在自然数的基本理论上加一个公理，似乎太武断了。我的意思是，我从来没有见过这样一种试图描述自然数的方法:“没有一个数等于它本身加3”作为一个基本前提。似乎应该是定理，而不是公理。
答案:
那是因为它是通过引入一个更一般的规则而引入的。具体来说，一阶算术有一个无限的公理模式——一个无限但可计算的公理模式。这个模型的每个公理说，对于一阶公式φ (x):
1.如果φ为0时为真，则为φ (0)。
2.只要φ在一个数上为真，在这个数之后也为真，即X: φ (X) → φ (SX)。
3.所以，φ在所有数∀n:φ(n:φ(n)中都是真的，即
(φ(0)∧(∀x:φ(x)→φ(sx))→(∀n:φ(n))
换句话说，对于每个公式，在0时为真，在每个使其为真的数时为真，所以在任何数时都为真。这就是一阶算术的归纳模式。作为特例，我们有这个归纳公理:
(0≠SSS 0∧(∀x:(x≠sssx)→(sx≠ssssx))→(∀n: n≠sssn)
好奇宝宝:
但这并不是说对于所有的n，n≠n+3。它给出了一些前提条件，然后根据这些前提条件可以得出最后的结论，但是我不知道那些前提条件在哪里。
答案:
啊，但是，利用算术的其他公理，我们证明那些前提条件，从而证明这个结论。公式(SSSx=x)在0处为假，因为0不是任何数字的后继数，包括SS0。同样，考虑到公式SSSSx=Sx，我们可以将其排列为S(SSSx)=S(x)。如果两个数有相同的后继，则相等，所以sssx = X .根据否定命题等价的逻辑规则:如果sx中的真证明X中的真，那么X中的假证明Sx中的假。所以那个公式在0是假的，假的时候它的后继也取一个假的值，所以按照一阶算术的归纳公理模式，它必然处处是假的。所以，一阶算术可以摆脱这样的模型:
好奇宝宝:
…我想我明白了。如果这个模型遵守我们已经指定的其他公理(他们没有去掉这个模型)，比如“零不是任何数的后继者”“两个有相同后继者的数相等”——那么我们可以证明公式x≠SSSx在0时成立，如果在X时成立，在x+1时也成立。所以，一旦我们进一步补充，公理x≠SSSx在0为真，如果x≠SSSx在Y为真，在Sy也为真，那么x≠SSSx在所有x都为真。…
答案:
我们得到了这些前提条件，所以我们得到结论X: X ≠ SSSX，从而去掉了所有的3-圈。对于任何N，类似的逻辑可以去除N个周期。”
好奇宝宝:
所以，我们去掉了所有的非标准自然数，只留下标准自然数？
答案:
不会。因为仍然存在与-2 *、-1 *、0 *和1 *的无限链相关的问题。
好奇宝宝:
这里有一个思路，可以用来摆脱无限链的模型。链中所有非标准自然数都大于标准自然数，对吗？例如，如果W是非标准自然数，那么W >；3，w & gt4.等等？
答案:
我们可以确凿地证明，没有一个数小于0，w不等于0，1，2，3，…，所以我必须同意。
好奇宝宝:
好的。我们还可以证明，如果x & gtY，那么x+z > Y+Z .所以如果我们有一个非标准数W，讨论w+w，那么w+w一定大于w+3，w+4等等。
所以w+w不可能是任何无限链的任何一部分，然后两个数相加应该会产生第三个数。
答案:
事实上，这证明了如果有一个无限链，就一定有两个无限链。换句话说，图中的原始模型本身不能作为一阶算术的模型。那个链条包含其他元素，展示这个并不代表它不存在。同样，既然所有的数都是奇数或偶数，那么我们肯定可以找到一个V使得v+v = w或者V+V+1 = W .所以V一定是另一个非标准链的一部分，它在包含w的标准链的前面。
好奇宝宝:
然而，这需要无限数量的非标准数链，所有这些链都大于任何标准数。也许我们可以把这个逻辑展开，最后得到一个矛盾，从而把无限链从头去掉——比如我们可以证明任何一个完全的非标准数类一定大于自身？
答案:
想法是好的，但不可行。你会得出一个结论，如果一个非标准数存在，那它一定是一个双向无限链的一部分，看起来就像是负整数和正整数的有序拷贝。如果无限链存在，那么对应于所有有理数的无限链也存在。所以，能作为一阶算术非标准模型的东西，必须至少包含标准数，后面是一个有理数的副本(每个有理数都用整数代替)。那么，加法和乘法在这个设定中都是有意义的——我们无法证明它可能比我们已经说过的更大。”
好奇宝宝:
好的，那么怎样才能去掉无限链的非标准自然数，只保留开头的标准自然数呢？他们会违反什么样的语句——什么样的公理可以消除多余的数？
答案:
为此，我们必须使用二阶逻辑。
好奇宝宝:
坦率地说，我不是100%清楚其中的区别。
答案:
好…之前你给了我一个可以检测奇数的公式。
好奇宝宝:
是Y: x = (2 * y)+1，在x=1，x=9时为真，以此类推，在x=0时为假。
答案:
当你根据数字的类别思考时，有些类别可以用公式来定义。例如，奇数{1，3，5，7，9，…}可以用这个带自由自变量的公式定义x: y: x = (2 * y)+1。不过，你也可以试着讨论一下数集{1，3，5，7，9，…}只就阶级理论而言，以及是否有公式定义。
好奇宝宝:
等一下，如果你不能定义一个公式来解释某个东西是否是这个集合的元素，你怎么能一个一个地谈论这个集合呢？我的意思是，从理性主义者的角度来看，这似乎不舒服。
答案:
嗯…还记得之前关于小猫的对话吗？
假设你说这样的话，‘有一类小猫，让任何一只小猫只喜欢这个类里的其他小猫’。给我一个满是小猫的房间，我可以统计所有可能的类，并检查你对每个类的声明，这样你就可以看到是否真的存在那样的类。所以这种说法是有意义的——它可以被否定或检查，它限制了现实的状态。但是你没有给我一个偏公式让我抓一只小猫，判断它是否在这个神秘的类里。我必须遍历小猫的所有类，才能找到满足你的语句的类。只有这样，我才能判断是否有任何特定的单一小猫在该类中。然而，那个陈述仍然是易错的，尽管在数学术语中，它不是直接的([1])——我们可以称之为，当你构造一个你只能通过调查许多可能的类来验证的陈述，并且你没有从一个你告诉我如何构造的特殊类开始。
好奇宝宝:
啊…是啊。如果在一个有无限只小猫的世界里，你不能在有限的时间内遍历所有可能的类，那该怎么办？
答案:
如果你说‘有一个班的小猫，他们都互相喜欢’，我可以展示一个班有三只互相喜欢的小猫，从而证明这种说法是正确的。如果你说，‘有一个班有四只小猫，它们互相喜欢，但不喜欢其他的猫’，鉴于小猫的其他特点，我也许可以提供一个建设性的证明来证明你的说法是错误的。每次你给我四只猫，我都能找到第五只猫，被你的四只猫中的一只喜欢，从而否定你的努力。但是，这就把我们带到了一个关于数学非常深入的部分，我们暂且不谈。重点是，即使在一个无限的世界里，在有限的时间里，仍然有二阶的陈述需要你去证明或证伪。一旦你承认那些特殊的二阶陈述是在有意义地解释某个东西，那么，也许，你就会承认一般的二阶陈述也是有意义的。
好奇宝宝:
…..这对我来说听起来有点奇怪。也许我们很快就会有麻烦了。
答案:
你不是唯一一个在这个问题上挣扎的数学家。
好奇宝宝:
但是让我们回到自然数。你说我们可以用二阶逻辑去掉任何无限链。
答案:
是的在二阶逻辑中，我们可以直接量化一个陈述句中所有可能的类，而不需要在所有公式中使用无限的公理模式:
∀p: p(0)∧(∀x: p(x)→p(sx))→(∀n: p(n))
p这里是任何一个类的语句，在每一个数里不是真就是假。任何一类数都对应一个语句，对于类内的数为真，对于类外的数为假。
好奇宝宝:
好…那么如何摆脱无限链呢？
答案:
因为，理论上不管有没有一阶公式来选取它们，还是有一类只包含标准数{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说是。如果我相信一阶逻辑有一个无限的公理模式，我能期待什么？
答案:
在这种情况下，你不相信有一个灵巧和紧凑的规则可以这样工作。但如果你相信那个二阶版本，你就相信没有人可以那样行动，即使他们是随机答题，或者分支宇宙在不同宇宙以不同方式回答，等等。顺便说一句，如果我们有一个有限的宇宙，也就是去掉每个数都有后继者的规则，转而假设256是唯一没有后继者的数——那么我们就可以在有限的时间内验证这个公理。
好奇宝宝:
我明白了。有没有办法用一阶逻辑摆脱无限链？我会发现这更容易处理，即使一开始看起来更复杂。
答案:
恐怕不行。我喜欢看的一种方式是:看模型如何局部约束，一阶逻辑可以做到，但只有二阶逻辑才能整体讲链、类、模型的性质。任何数是否有后继都是局部性质——从数的角度看模型是什么样的？一个数加三是否等于它本身是一个问题:你可以从任何数自身的位置来评价它。一个数是不是偶数，可以通过寻找一个唯一的数X使得x+x等于那个数来回答。然而，当你试图说只有一个唯一的链，从0开始，你是在试图借助连通性和链的思想来描述非局部性质，这需要指定一个关于可能类的逻辑。
好奇宝宝:
嗯。但是如果所有的局部属性都相同，为什么要担心整体属性呢？在一阶逻辑中，任何“局部”公式在0和所有“自然”后继者处为真，并且在所有断开的链中也必须为真…对吗？还是我做错了？除了0链以外的所有链——所有‘非标准数’——都将具有与‘自然数’相同的性质，对吗？
答案:
恐怕不行。算术的一阶公理无法成功判定一个图灵机会是否停止——是否存在一个时刻停止一个图灵机。在标准数中，从我们的角度来看，一个图灵机‘真的不会停’——它不会停在0点、1点、2点，以及0链上的所有标准后继者。在整数的非标准模型中——一个有其他无限链的模型——在非标准链中可能有一个位置，图灵机在这个位置停止，并且总是停止。
在这个与一阶公理完全兼容且不能被它们移除的新模型中，图灵机对于任意数t都是运行的，并且在t+1仍然是运行的，这是不成立的。虽然我们可以把注意力限制在‘自然’数上，但是我们可以发现，这个图灵机在0、1、2、0链之后的每一个时刻都在运行。
好奇宝宝:
好…我不确定会有什么后果。
答案:
意味着很多在标准时间内永不停止的图灵机，仅凭一阶推理是无法证明其不停止的，因为它们的不停止性质无法从一阶公理中推导出来。逻辑是关于从前提得出的结论，记得吗？这意味着你将无法证明——你不应该证明——图灵机停止，只使用一阶逻辑。
好奇宝宝:
如何证明不成立？我是说，那些证据在哪里失效了？
答案:
你不会得到归纳中的第二步，‘对于任何时刻，T图灵机都在运行，在t+1时刻它仍然会运行’。非标准数为t的非标准模型的存在否定了这个前提条件——图灵机在非标准时间停止运行。如果能把注意力限制在标准数上，我们会发现图灵机运行在0，1，2等等。
、
好奇宝宝:
但是如果一个图灵机真的停了，会有一个停的时刻，比如步骤97。
答案:
是的但是97存在于所有算术的非标准模型中，所以我们可以在一阶逻辑中证明它的存在。0是一个数，每个数都有后继，数不循环，以此类推，那么就会有97。每个非标准模型至少包含一个标准数。所以当图灵机确实停止时，你可以证明它在一阶算术中停止——它是从那些前提中推导出来的。这正是你所期待的，假设你能观察到那个图灵机的97步。当一个图灵机实际停止时，你应该能够证明它停止，而不用担心无限的未来时间！当它实际上并没有停在标准数内——由于‘非标准停机’的存在，就成了问题。所以图灵机会一直运行的结论可能事实上并不是从一阶算术推导出来的，因为你可以遵循一阶算术的所有前提，但是在非标准模型的某个地方还是有图灵机会停下来的。
好奇宝宝:
所以二阶算术比一阶算术更强大。从前提可以推导出什么？
答案:
谈论可能性较小的模型的能力必然会导致这种情况。正如有人所写的，“一个苹果是真的，另一个苹果不一定是真的；因此，一个苹果比世界上所有的苹果更值得一提。“如果你能把你的宇宙限制在更窄的一类模型中，那么必然会有更多的事实可以推导出来，因为你所说的模型越大，关于它们的事实就越少。另外，二阶算术比一阶算术证明了更多的定理，而且确实是真的——比如可以证明一个可以计算古德斯坦序列的图灵机总是达到0而停止，大力神总是赢得九头蛇游戏。但是，如果笼统地说二阶逻辑其实比一阶逻辑更强大，就会有一些争议。
好奇宝宝:
好吧。毕竟，没有人发明过一阶公式来摆脱所有非标准数，并不意味着永远不可能。在未来，一些聪明的数学家可能会找到一种方法，通过使用加法，乘法和其他单个数字是否存在，对任何数字x只做局部的事情。这个方法可以告诉我们那个数是在0链上还是在双向无限链上。这很简单:
(a=b*c)
答案:
不，那不会发生的。
好奇宝宝:
但是，或许，你可以找到一些完全不同的创新方式，只用一阶公理就可以得到全是标准自然数的模型。
答案:
不会吧。
好奇宝宝:
良好的…你怎么知道的？我的意思是，当你参加比赛时，作为参赛者的一个原则是，当一些事情看起来不可能时，你不要放弃。我无法理解如何用一阶公式来检验无限链。但是，我之前没想到你能去掉有限圆。一旦你解释了，就很简单了。毕竟，“不可能”这个词有两种不同的用法。一个是用已有的知识来说明某件事不能实现，也就是说即使你是超级特工，也不可能找到实现这个目标的方法。在这种情况下，你需要用已知的知识给出一个确定的、完整的结果，这样你就可以否定每一种可能的成功方式。还有一种方式，‘不可能’这个词更常用:你想了五秒钟也找不到实现的方法，然后说‘不可能’。总的来说，知识是有限的，那个问题似乎有些神秘。
答案:
是的用一阶公式摆脱双向无限链是第一种不可能。我们知道这永远不会实现。
好奇宝宝:
是啊，我知道。好吧，你有什么看法？你如何解释你的观点？你能用你清晰的知识回答为什么‘不可能’吗？别这么神神秘秘的逼好吗？
答案:
下次，下次再说吧。
译者注:
[1]间接(有见地)
[2]原初宇宙在某些情况下既可以翻译为宇宙，也可以翻译为宇宙。有些时候，很难选择，或者是一语双关。请你自己记住这一点。
关注多多数学网，每天获取更多有趣的数学文章。
