0123可以组成多少无重复的自然数（由0123组成的无重复数字的自然
自然数包括哪些？ 为什么自然数是0、1、2、3……这些，能不能有别的？
***作者Eliezer Yudkowsky，AI专家。
翻译作者，风无名，哆嗒数学网翻译组成员。
校对Math001
关注 哆嗒数学网 每天获得更多数学趣文
解答者
噢！你好！又回来啦？
好奇宝宝
是的，我又有新问题了。之前你说你不得不使用二阶逻辑来定义自然数。不过，我非常确信我听说过叫做“一阶皮亚诺算术”的东西，据说它定义了自然数。从名字上说，它不应该含有任何“二阶”公理。坦白地说，我觉得我对这个二阶的东西还是一点感觉都没有。
解答者
好吧，让我们通过考察如下的模型来开始
这个模型拥有那三个我们希望对于标准自然数都满足的性质“每一个数都有一个后继”， ”如果两个数拥有一样的后继，则相等”，”0是那个唯一的不是其它数的后继的数。”。在这个模型中，所有这些陈述都是真的，所以从那个意义上，它的确和自然数差不多
显然这个模型不是我们正在寻找的自然数，因为它拥有多余的一些神秘的数，像C， 2。像C那样的东西甚至是一个圈，我不希望任何自然数会这样。而且，还存在双向无穷的不能收拢到任何其它的东西的一条链。
是的，这就是一阶逻辑与二阶逻辑的区别在一阶逻辑中，我们可以去除那些ABC——做一个陈述句，它可以排除掉任何拥有像那样的圈的模型。我们不能去除掉下面的无穷的链。在二阶逻辑中，我们可以去掉多那个多余的链。
好奇宝宝
你能解释一下你刚刚说的吗，虽然眼下我还不知道二阶逻辑是什么。
解答者
再等我一下。，细想下面这个检验“二性质”的公式
x + 2 = x 2
好奇宝宝
换句话说，当x等于2的时候，这个公式是真的，其它任何地方它是假的，所以它单独挑选出2 ？
解答者
正是。下面这个是一个检查奇数的公式
?y: x=(2y)+1
好奇宝宝
嗯，OK.这个公式在说，“存在一个y，使得x等于2乘以y加上1”。当x是1的时候，那是真的，因为0是一个数，而且1=(20) + 1.当x是9的时候，那是真的，因为存在一个数4，使得(24)+1...正确的。只要x取奇数那个公式就是真的，而且只对x取奇数时是真的。
解答者
非常正确。现在假定我们有一个办法来检查在一个模型中ABC-圈的存在——在ABC-圈都是真的其它地方都是假的的公式。然后，我可以改造一下这个公式，得到它的否定形式，即“任何像这样的对象都不允许存在“，增�***顾搿懊恳桓鍪加幸桓龊蠹獭罢庑┮黄鹱魑匀皇墓怼�
好奇宝宝
嗯，我可以通过表述??x:(x=A)来去除ABC-圈吗？
解答者
嗯，只有你已经告诉了我A是什么才可以那么说，而且在一个去除了所有带有圈的模型的逻辑中，你不能指定某个特定的不存在的对象。
好奇宝宝
这样啊。OK...所以那些去除后继的圈的思路是...嗯。在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)，即
(Φ(0) ∧ (?x: Φ(x) → Φ(Sx))) → (?n: Φ(n))
换句话说，对于每一个公式，它在0时真的，它在每一个使它为真的下一个数都是真的，那么它在任何一个数都是真的。这就是一阶算术的归纳模式。作为一个特例，我们有这个归纳公理:
(0≠SSS0 ∧ (?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是一个非标准自然数，那么wgt3, wgt4，等等？
解答者
我们可以归纳地证明没有一个数小于0，并且w不等于0、1、2、3、……，所以我必须同意那一点。
好奇宝宝
OK.我们也能够证明如果xgty,那么x+z gt y+z.所以如果我们有一个非标准数w并且讨论w+w, 那么w+w一定大于w+3, w+4等等。
所以w+w不能是哪个无穷链的任何部分，然后相加两个数应该产生第三个数。
解答者
事实上，那就证明了，如果存在一个无穷链，那就必然存在两个无穷链。换句话说，图片里面最原始的那个模型，仅仅它自己是不能作为一阶算术的模型的。那个链蕴含着其它的元素，展示了这一点不意味着证明了那个链不存在。类似地，由于所有的数为奇数或者偶数，我们一定可以找到一个v使得v+v = w 或者v + v + 1 = w。于是v必然是另一个非标准链的一部分，这个非标准链在那个含有w的标准链的前面。
好奇宝宝
不过，那就要求有无穷多个无穷非标准数的链，这些非标准数都大于任何标准数。也许我们可以扩展这个逻辑，最终获得一个矛盾，从而一开始就去除无穷链 —— 比如，我们可以证明任何完备的非标准数的类必定大于它自己？
解答者
想法很好，不过，并不可行。你将得到这样的结论如果一个非标准数存在，它必定是一个双向无穷的链的一部分，这个链看起来像是负整数与正整数的有序拷贝。如果一个无穷链存在，那么存在对应于所有有理数的无穷多个链。所以呢，可以作为一阶算术的非标准模型的某个东西，必定至少含有标准数，紧接着一个有理数的拷贝（每一个有理数都被一个整数所代替）。然后，加法、乘法在这个设定中都走得通——我们不能证明它可能比我们已经说过的更大。”
好奇宝宝
OK, 那么我们如何才能去除掉无穷多个无穷链的非标准自然数、仅仅保留开始的标准自然数呢？它们将违反什么样的陈述句——什么类型的公理才可以排除掉多余的数呢？
解答者
为此，我们必须使用二阶逻辑。
好奇宝宝
坦白地说，我不是100%地清楚它们的区别。
解答者
OK...早先你给我一个可以检测出奇数的公式。
好奇宝宝
是的。?y: x=(2y)+1，在x=1，x=9等等地方为真，不过在x=0为假。
解答者
当你依据数的类来思考的时候，那就存在一些能够被公式所定义的类。例如，奇数 {1, 3, 5, 7, 9, ...}的类可以被这个带有自由变元x的公式所定义 ?y: x=(2y)+1。不过呢，你也可以试着去仅仅就类论类地讨论{1, 3, 5, 7, 9, ...}这个数集，是否存在一个定义了它的公式。
好奇宝宝
等一下，如果你不能定义一个说明了某些东西是否是这个 的元素的公式，你怎么能谈论一个一个 呢？我的意思是，从理性主义者的视角来看，那样貌似感觉不爽。
解答者
嗯...还记得先前关于小猫的谈话吗？
假定你像这样谈说，‘存在一个小猫的类，使得任何一只小猫只喜欢这个类中的其它小猫’。给我一个装满小猫的屋子，我可以计数出所有可能的类，对于每一个类检查你的陈述，这样就可以看到是否真的存在一个像那样说的类。所以那个陈述句是有意义的——它是可以被否定或者检查的，它限制了实在的状态。不过你并没有给我一个局部的公式以便我抓起一只小猫就能判断它是否在这个神秘的类之中。我必须遍历所有的小猫的类来寻找满足你的陈述句的类，只有到那时，我才能判断任何具体的单只小猫是否在那个类中。不过那个陈述句仍然有可错性，虽然使用数学的术语，它是非直谓的([译注1])——以下情况我们才能那样称呼它当你构造了一个你只能通过考察很多可能的类来核实的陈述句，并没有从一个特殊的、你告诉了我如何构造的类来开始。
好奇宝宝
啊... 嗯。如果是在有无穷只小猫的世界里，你不能在有限时间内遍历所有可能的类呢？
解答者:
如果你说，‘存在一个小猫的类，它们都互相喜欢’，我可以展示出来一个拥有三只小猫的彼此喜欢的类，于是就证明了那个陈述句是正确的。如果你说‘存在一个类，它有四只小猫，它们互相喜欢但不喜欢别的猫’，在已经知道小猫的其它特性的情况下，我也许可以提供一个构造性的证明来证明你的陈述是错的；每次，你给我四只猫，我可以找到第五只猫，它被你的四只猫的一只所喜欢，从而否定了你的努力。不过，这就把我们带到了关于数学的非常深入的部分了，我们暂时不去讲它。重点是即使是无穷的世界里，仍然存在二阶的陈述让你在有限时间内证明或证否。一旦你承认那些特殊的二阶陈述句是在有意义地说明一些东西，好吧，也许，你会承认一般的二阶陈述句也是有意义的。
好奇宝宝
……对我来说那听起来有点怪怪的，也许不久以后我们会遇到麻烦。
解答者
你不是唯一一个纠结这个的“数学家”。
好奇宝宝
不过让我们回到自然数吧。你说我们可以使用二阶逻辑来去除任何的无穷链。
解答者
是的。在二阶逻辑中，我们可以在一条陈述句中，直接对所有可能的类进行量化，而不必使用所有公式上的无穷的公理模式
?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=bc)
解答者
不。那不会发生。
好奇宝宝
不过，也许，你能否找到一些完全不同的创新的方式，只用一阶公理得到全部都是标准自然数的模型。
解答者
不可能。
好奇宝宝
嗯...你是如何准确地知道那一点的？我的意思是，当你参加一个比赛，作为比赛选手的一条原则就是当某事看起来不可能的时候，你不要放弃。我不能明白如何使用一阶公式来检查无穷的链。不过，先前我不能认为你可以去除有限圈，一旦你讲解了，它就显得非常简单。毕竟，关于‘不可能’这个词存在两种不同的用法，一种直接用已有知识表明了某事不能实现，也就是说哪怕你是一个超级智能体，也不可能找一种做法来达成这个目标。这种情况，你需要利用已知知识给出一个确定、完整的结果，从而你可以否定每一个可能的成功途径。还有一种，‘不可能’一词更加通常的用法你思考了五秒钟没有发现实现它的 ，然后就说”不可能“。一般在对知识了解有限，那个问题又看起来有些神秘主义倾向会这样。
解答者
是的。使用一阶公式来去除掉双向无穷链，是之一种类型的不可能。我们知道它永远不可能实现。
好奇宝宝
嗯，我知道。好吧，你有什么观点，如何说明你的观点？能用你明确的知识正面回答为什么‘不可能’吗？别用这种神秘兮兮的方式强行灌输？
解答者
下一次，下一次我们再来好好讲讲。
译者注
[1]非直谓的(impredicative)
[2]***universe既可以翻译为宇宙，也可以在某些情况下翻译为“论域”。有些情况下，难以抉择，或者本身就是双关。请读者自己记住这一点。
关注 哆嗒数学网 每天获得更多数学趣文
由0123组成的无重复数字的自然数 为什么非0自然数都是奇偶排列