原文作者：Eliezer Yudkowsky，AI專家。

翻譯作者，風(fēng)無名，哆嗒數(shù)學(xué)網(wǎng)翻譯組成員。

校對(duì)：Math001

關(guān)注 哆嗒數(shù)學(xué)網(wǎng) 每天獲得更多數(shù)學(xué)趣文

解答者：

噢！你好！又回來啦？

好奇寶寶：

是的，我又有新問題了。之前你說你不得不使用二階邏輯來定義自然數(shù)。不過，我非常確信我聽說過叫做“一階皮亞諾算術(shù)”的東西，據(jù)說它定義了自然數(shù)。從名字上說，它不應(yīng)該含有任何“二階”公理。坦白地說，我覺得我對(duì)這個(gè)二階的東西還是一點(diǎn)感覺都沒有。

解答者：

好吧，讓我們通過考察如下的模型來開始：

這個(gè)模型擁有那三個(gè)我們希望對(duì)于標(biāo)準(zhǔn)自然數(shù)都滿足的性質(zhì)“每一個(gè)數(shù)都有一個(gè)后繼”， ”如果兩個(gè)數(shù)擁有一樣的后繼，則相等”，”0是那個(gè)唯一的不是其它數(shù)的后繼的數(shù)。”。在這個(gè)模型中，所有這些陳述都是真的，所以從那個(gè)意義上，它的確和自然數(shù)差不多

顯然這個(gè)模型不是我們正在尋找的自然數(shù)，因?yàn)樗鼡碛卸嘤嗟囊恍┥衩氐臄?shù)，像C， 2*。像C那樣的東西甚至是一個(gè)圈，我當(dāng)然不希望任何自然數(shù)會(huì)這樣。而且，還存在雙向無窮的不能收攏到任何其它的東西的一條鏈。

是的，這就是一階邏輯與二階邏輯的區(qū)別：在一階邏輯中，我們可以去除那些ABC——做一個(gè)陳述句，它可以排除掉任何擁有像那樣的圈的模型。但是我們不能去除掉下面的無窮的鏈。在二階邏輯中，我們可以去掉多那個(gè)多余的鏈。

好奇寶寶：

你能解釋一下你剛剛說的嗎，雖然眼下我還不知道二階邏輯是什么。

解答者：

再等我一下。首先，細(xì)想下面這個(gè)檢驗(yàn)“二性質(zhì)”的公式：

x 2 = x * 2

好奇寶寶：

換句話說，當(dāng)x等于2的時(shí)候，這個(gè)公式是真的，其它任何地方它是假的，所以它單獨(dú)挑選出2 ？

解答者：

正是。下面這個(gè)是一個(gè)檢查奇數(shù)的公式：

?y: x=(2*y) 1

好奇寶寶：

嗯，OK.這個(gè)公式在說，“存在一個(gè)y，使得x等于2乘以y加上1”。當(dāng)x是1的時(shí)候，那是真的，因?yàn)?是一個(gè)數(shù)，而且1=(2*0) 1.當(dāng)x是9的時(shí)候，那是真的，因?yàn)榇嬖谝粋€(gè)數(shù)4，使得(2*4) 1…正確的。只要x取奇數(shù)那個(gè)公式就是真的，而且只對(duì)x取奇數(shù)時(shí)是真的。

解答者：

非常正確。現(xiàn)在假定我們有一個(gè)辦法來檢查在一個(gè)模型中ABC-圈的存在——在ABC-圈都是真的其它地方都是假的的公式。然后，我可以改造一下這個(gè)公式，得到它的否定形式，即“任何像這樣的對(duì)象都不允許存在“，增加它，使它與“每一個(gè)數(shù)都有一個(gè)后繼“這些一起作為自然數(shù)的公理。

好奇寶寶：

嗯，我可以通過表述??x:(x=A)來去除ABC-圈嗎？

解答者：

嗯，只有你已經(jīng)首先告訴了我A是什么才可以那么說，而且在一個(gè)去除了所有帶有圈的模型的邏輯中，你不能指定某個(gè)特定的不存在的對(duì)象。

好奇寶寶

這樣啊。OK…所以那些去除后繼的圈的思路是…嗯。在0，1，2，3這些數(shù)中，0不是任何數(shù)的后繼。如果我有一組次從1開始的數(shù)，比如{1,2,3 …}, 在這個(gè)組中，1不是任何數(shù)的后繼。在A，B，C，數(shù)A是數(shù)C的后繼，數(shù)C是數(shù)B的后繼，數(shù)B是數(shù)A的后繼，如果我說”不存在數(shù)的組G，使得對(duì)于G中的任何數(shù)x，它是G中另外一個(gè)數(shù)y的后繼。“

解答者：

啊！非常聰明。不過，你剛才就在使用二階邏輯，因?yàn)槟阏務(wù)摿藢?shí)體的組或類，一階邏輯僅僅談?wù)搯蝹€(gè)的實(shí)體。假定我們有一個(gè)談?wù)撔∝堃约八麄兪欠袷怯懭藚挼倪壿嫛＿@是一個(gè)恰好含有三個(gè)不同的都是討人厭的小貓的論域的模型：

好奇寶寶：

嗯，那些“屬性”(圖中的“propery”)是什么？

解答者：

它們是小貓的所有可能的類。它們被稱為屬性，因?yàn)樾∝埖拿恳粋€(gè)類都對(duì)應(yīng)了那類小貓具有的、其他類小貓不具有的屬性。比如右上角的那個(gè)只含有灰色小貓的類，就對(duì)應(yīng)了一個(gè)在灰色小貓為真而在其它地方為假的某個(gè)陳述，也對(duì)應(yīng)了一個(gè)只有灰色小貓具有、其它小貓不具有的屬性。事實(shí)上，從現(xiàn)在開始我們認(rèn)為一個(gè)“屬性”僅僅說了一個(gè)“類”

好奇寶寶：

好，我理解了“小貓的類”這個(gè)概念了。

解答者：

在一階邏輯中，我們可以談?wù)搯蝹€(gè)的貓，它與其它單個(gè)貓的關(guān)系，符合某個(gè)特殊關(guān)系的貓是否存在。在二階邏輯中，我們可以談?wù)撠埖念悾约澳承╊愂欠翊嬖凇Ｋ裕谝浑A邏輯中，我能說，“存在一只不討人厭的貓”或者“對(duì)于任意一只貓，它都是不討人厭的”或者“對(duì)于任意一只貓，存在另外一只貓它喜歡第一只貓”。不過，需要二階邏輯才形成關(guān)于“貓的類”的敘述句，比如“不存在一個(gè)貓的類，使得該類中的每一個(gè)貓都被該類中的另一只貓所喜歡”

好奇寶寶：

我懂了。所以，當(dāng)我想說你不能擁有任何數(shù)的組，使得這個(gè)組中的任一個(gè)數(shù)都是這個(gè)組中的其它某個(gè)數(shù)的后繼…

解答者：

……你對(duì)數(shù)的類是否存在進(jìn)行了量化描述，這意味著你在使用二階邏輯。不過，就這個(gè)情形來說，僅使用一階邏輯來去除ABC-圈，也是容易的，可能的。考察這個(gè)公式：

x=SSSx

好奇寶寶：

x 加3與它自己相等？

解答者：

對(duì)的。這是一個(gè)一階公式，因?yàn)樗鼪]有談?wù)擃悺Ｔ?，1，2，3…這個(gè)公式是假的，不過在A,B,C它是真的。

好奇寶寶：

圖中的那個(gè)加號(hào)“ ”是什么意思？

解答者：

嗯，我試圖使用加號(hào)“ ”來說“這公式是真的”，類似的， 假定“?”的意思是那個(gè)公式是假的。一個(gè)普通的想法是，我們現(xiàn)在有一個(gè)公式來檢查3-圈，把它們與像0，1，2這樣的標(biāo)準(zhǔn)數(shù)區(qū)分開來。

好奇寶寶：

我明白了。所以，通過添加??x:x=SSSx作為一條新的公理，所有含有A,B,C或者任何其它的非標(biāo)準(zhǔn)數(shù)的3-圈的模型，我們就可以都去除了。

解答者：

是的。

好奇寶寶：

不過，這樣向自然數(shù)的基礎(chǔ)理論添加一條公理，好像過于隨意。我的意思是，我從來沒有看到過這樣描述自然數(shù)的嘗試：把“沒有一個(gè)數(shù)等于它自己加3”作為一個(gè)基本的前提。看起來它應(yīng)該是一條定理，而不是公理。

解答者：

那是因?yàn)樗峭ㄟ^引入一個(gè)更加一般的的規(guī)則來引入的。具體來說，一階算術(shù)有一個(gè)無窮公理模式——一個(gè)無窮但是可計(jì)算的公理模式。這個(gè)模式的每一條公理說了，對(duì)于一個(gè)一階公式Φ(x)：

1. 如果Φ在0是真的，即Φ(0)

2. 只要Φ在一個(gè)數(shù)時(shí)為真，則在這個(gè)數(shù)的后繼也為真，即?x: Φ(x)→Φ(Sx)

3. 那么，Φ在所有數(shù)都是真的: ?n: Φ(n)，即

(Φ(0) ∧ (?x: Φ(x) → Φ(Sx))) → (?n: Φ(n))

換句話說，對(duì)于每一個(gè)公式，它在0時(shí)真的，它在每一個(gè)使它為真的下一個(gè)數(shù)都是真的，那么它在任何一個(gè)數(shù)都是真的。這就是一階算術(shù)的歸納模式。作為一個(gè)特例，我們有這個(gè)歸納公理:

(0≠SSS0 ∧ (?x: (x≠SSSx) → (Sx≠SSSSx)) → (?n: n≠SSSn)

好奇寶寶:

不過那并沒有說對(duì)于所有的n， n≠n 3。它給出了一些前提條件，然后根據(jù)這些前提能可以得出最后那個(gè)結(jié)論，但是我并不知道那些前提條件在哪里。

解答者:

啊，然而，使用算術(shù)的其它公理，我們證明那些前提條件，從而證明了這個(gè)結(jié)論。公式(SSSx=x)在0是假的，因?yàn)?不是任何數(shù)的后繼，包括SS0。類似地，考慮公式SSSSx=Sx，我們可以整理為S(SSSx)=S(x)。如果兩個(gè)數(shù)有相同的后繼則它們是相等的，于是SSSx=x。根據(jù)逆否命題等價(jià)的邏輯規(guī)則：如果在Sx的真實(shí)性證明了在x的真實(shí)性，那么，在x為假就證明了在Sx為假。于是那個(gè)公式在0是假的，當(dāng)它是假的時(shí)候它的后繼也取值為假，于是根據(jù)一階算術(shù)的歸納公理模式它必然處處為假。所以，一階算術(shù)可以去掉像這樣的模型：

好奇寶寶：

…嗯，我認(rèn)為我明白了。如果這個(gè)模型遵守了我們已經(jīng)指定了的其它公理（它們沒有去除掉這個(gè)模型），比如“零不是任何數(shù)的后繼”、“擁有同樣后繼的兩個(gè)數(shù)相等”——那么我們可以證明公式x≠SSSx 在0是真的，可以證明那個(gè)公式如果在x是真的那么在x 1也是真的。所以，一旦我們更進(jìn)一步地添加公理x≠SSSx在0是真的，以及如果x≠SSSx在y是真的則在Sy也是真的，那么x≠SSSx在所有的x都是真的…

解答者：

我們已經(jīng)得到了這些前提條件了，所以我們得到了那個(gè)結(jié)論 ?x: x≠SSSx，從而去除了所有的3-圈。對(duì)于任意的N，類似的邏輯可以去除N-圈。”

好奇寶寶：

所以，我們?nèi)コ怂械姆菢?biāo)準(zhǔn)自然數(shù)、只留下了標(biāo)準(zhǔn)自然數(shù)?

解答者：

不。因?yàn)檫€存在與-2*, -1*, 0*, 1* 這個(gè)無窮鏈相關(guān)的問題。

好奇寶寶：

這里有一個(gè)想法可以用來去除掉帶有無窮鏈的模型。鏈中的所有非標(biāo)準(zhǔn)自然數(shù)都大于標(biāo)準(zhǔn)自然數(shù)，對(duì)吧？比如，如果w是一個(gè)非標(biāo)準(zhǔn)自然數(shù)，那么w>3, w>4，等等？

解答者：

我們可以歸納地證明沒有一個(gè)數(shù)小于0，并且w不等于0、1、2、3、……，所以我必須同意那一點(diǎn)。

好奇寶寶：

OK.我們也能夠證明：如果x>y,那么x z > y z.所以如果我們有一個(gè)非標(biāo)準(zhǔn)數(shù)w并且討論w w, 那么w w一定大于w 3, w 4等等。

所以w w不能是哪個(gè)無窮鏈的任何部分，然后相加兩個(gè)數(shù)應(yīng)該產(chǎn)生第三個(gè)數(shù)。

解答者：

事實(shí)上，那就證明了，如果存在一個(gè)無窮鏈，那就必然存在兩個(gè)無窮鏈。換句話說，圖片里面最原始的那個(gè)模型，僅僅它自己是不能作為一階算術(shù)的模型的。那個(gè)鏈蘊(yùn)含著其它的元素，展示了這一點(diǎn)不意味著證明了那個(gè)鏈不存在。類似地，由于所有的數(shù)為奇數(shù)或者偶數(shù)，我們一定可以找到一個(gè)v使得v v = w 或者v v 1 = w。于是v必然是另一個(gè)非標(biāo)準(zhǔn)鏈的一部分，這個(gè)非標(biāo)準(zhǔn)鏈在那個(gè)含有w的標(biāo)準(zhǔn)鏈的前面。

好奇寶寶：

不過，那就要求有無窮多個(gè)無窮非標(biāo)準(zhǔn)數(shù)的鏈，這些非標(biāo)準(zhǔn)數(shù)都大于任何標(biāo)準(zhǔn)數(shù)。也許我們可以擴(kuò)展這個(gè)邏輯，最終獲得一個(gè)矛盾，從而一開始就去除無窮鏈 —— 比如，我們可以證明任何完備的非標(biāo)準(zhǔn)數(shù)的類必定大于它自己？

解答者：

想法很好，不過，并不可行。你將得到這樣的結(jié)論：如果一個(gè)非標(biāo)準(zhǔn)數(shù)存在，它必定是一個(gè)雙向無窮的鏈的一部分，這個(gè)鏈看起來像是負(fù)整數(shù)與正整數(shù)的有序拷貝。如果一個(gè)無窮鏈存在，那么存在對(duì)應(yīng)于所有有理數(shù)的無窮多個(gè)鏈。所以呢，可以作為一階算術(shù)的非標(biāo)準(zhǔn)模型的某個(gè)東西，必定至少含有標(biāo)準(zhǔn)數(shù)，緊接著一個(gè)有理數(shù)的拷貝（每一個(gè)有理數(shù)都被一個(gè)整數(shù)所代替）。然后，加法、乘法在這個(gè)設(shè)定中都走得通——我們不能證明它可能比我們已經(jīng)說過的更大。”

好奇寶寶：

OK, 那么我們?nèi)绾尾拍苋コ魺o窮多個(gè)無窮鏈的非標(biāo)準(zhǔn)自然數(shù)、僅僅保留開始的標(biāo)準(zhǔn)自然數(shù)呢？它們將違反什么樣的陳述句——什么類型的公理才可以排除掉多余的數(shù)呢？

解答者：

為此，我們必須使用二階邏輯。

好奇寶寶：

坦白地說，我不是100%地清楚它們的區(qū)別。

解答者：

OK…早先你給我一個(gè)可以檢測(cè)出奇數(shù)的公式。

好奇寶寶：

是的。?y: x=(2*y) 1，在x=1，x=9等等地方為真，不過在x=0為假。

解答者：

當(dāng)你依據(jù)數(shù)的類來思考的時(shí)候，那就存在一些能夠被公式所定義的類。例如，奇數(shù) {1, 3, 5, 7, 9, …}的類可以被這個(gè)帶有自由變?cè)獂的公式所定義： ?y: x=(2*y) 1。不過呢，你也可以試著去僅僅就類論類地討論{1, 3, 5, 7, 9, …}這個(gè)數(shù)集，是否存在一個(gè)定義了它的公式。

好奇寶寶：

等一下，如果你不能定義一個(gè)說明了某些東西是否是這個(gè)集合的元素的公式，你怎么能談?wù)撘粋€(gè)一個(gè)集合呢？我的意思是，從理性主義者的視角來看，那樣貌似感覺不爽。

解答者：

嗯…還記得先前關(guān)于小貓的談話嗎？

假定你像這樣談?wù)f，‘存在一個(gè)小貓的類，使得任何一只小貓只喜歡這個(gè)類中的其它小貓’。給我一個(gè)裝滿小貓的屋子，我可以計(jì)數(shù)出所有可能的類，對(duì)于每一個(gè)類檢查你的陳述，這樣就可以看到是否真的存在一個(gè)像那樣說的類。所以那個(gè)陳述句是有意義的——它是可以被否定或者檢查的，它限制了實(shí)在的狀態(tài)。不過你并沒有給我一個(gè)局部的公式以便我抓起一只小貓就能判斷它是否在這個(gè)神秘的類之中。我必須遍歷所有的小貓的類來尋找滿足你的陳述句的類，只有到那時(shí)，我才能判斷任何具體的單只小貓是否在那個(gè)類中。不過那個(gè)陳述句仍然有可錯(cuò)性，雖然使用數(shù)學(xué)的術(shù)語，它是非直謂的([譯注1])——以下情況我們才能那樣稱呼它：當(dāng)你構(gòu)造了一個(gè)你只能通過考察很多可能的類來核實(shí)的陳述句，并沒有從一個(gè)特殊的、你告訴了我如何構(gòu)造的類來開始。

好奇寶寶：

啊… 嗯。如果是在有無窮只小貓的世界里，你不能在有限時(shí)間內(nèi)遍歷所有可能的類呢？

解答者:

如果你說，‘存在一個(gè)小貓的類，它們都互相喜歡’，我可以展示出來一個(gè)擁有三只小貓的彼此喜歡的類，于是就證明了那個(gè)陳述句是正確的。如果你說‘存在一個(gè)類，它有四只小貓，它們互相喜歡但不喜歡別的貓’，在已經(jīng)知道小貓的其它特性的情況下，我也許可以提供一個(gè)構(gòu)造性的證明來證明你的陳述是錯(cuò)的；每次，你給我四只貓，我可以找到第五只貓，它被你的四只貓的一只所喜歡，從而否定了你的努力。不過，這就把我們帶到了關(guān)于數(shù)學(xué)的非常深入的部分了，我們暫時(shí)不去講它。重點(diǎn)是即使是無窮的世界里，仍然存在二階的陳述讓你在有限時(shí)間內(nèi)證明或證否。一旦你承認(rèn)那些特殊的二階陳述句是在有意義地說明一些東西，好吧，也許，你會(huì)承認(rèn)一般的二階陳述句也是有意義的。

好奇寶寶：

……對(duì)我來說那聽起來有點(diǎn)怪怪的，也許不久以后我們會(huì)遇到麻煩。

解答者：

你不是唯一一個(gè)糾結(jié)這個(gè)的“數(shù)學(xué)家”。

好奇寶寶：

不過讓我們回到自然數(shù)吧。你說我們可以使用二階邏輯來去除任何的無窮鏈。

解答者：

是的。在二階邏輯中，我們可以在一條陳述句中，直接對(duì)所有可能的類進(jìn)行量化，而不必使用所有公式上的無窮的公理模式：

?P: P(0) ∧ (?x: P(x) → P(Sx)) → (?n: P(n))

這里的P是任何一個(gè)類的陳述，它在每一個(gè)數(shù)要么真要么假。數(shù)的任何一個(gè)類，都對(duì)應(yīng)了一個(gè)陳述，對(duì)于類里面的數(shù)它為真，對(duì)于類外面的數(shù)它為假。

好奇寶寶：

OK…那是如何去除掉無窮鏈的呢？

解答者：

因?yàn)椋瑥睦碚撋险f，無論是否存在一個(gè)一階公式能把它們挑選出來，仍然存在一個(gè)包含、且僅包含了標(biāo)準(zhǔn)數(shù){0, 1, 2, …}的類。如果你把類當(dāng)作一個(gè)陳述P，那么P在0是真的——那就是說，0是標(biāo)準(zhǔn)數(shù)中。如果200是一個(gè)標(biāo)準(zhǔn)數(shù)則201也是等等；如果P在x是真的，也在x 1是真的。另一方面，如果你把‘僅在在標(biāo)準(zhǔn)數(shù)’這個(gè)類當(dāng)作一個(gè)陳述，它在 -2*, -1*, 0*等等都是假的——那些數(shù)不在這個(gè)理論上的類中。所以‘如果它在0*為真則它在1*為真’就是為真了，因?yàn)樵?*它不為真。于是我們以下圖來終結(jié)：

所以這個(gè)二階公理……

?P: P0 ∧ (?x: Px → P(Sx)) → (?n: Pn)

……一下子就去除掉了任何不鏈接的鏈、有限圈，即任何非標(biāo)準(zhǔn)數(shù)。

好奇寶寶：

不過那條公理的準(zhǔn)確意思是？我的意思是，暫時(shí)放棄短語‘標(biāo)準(zhǔn)自然數(shù)’，假定我對(duì)那些沒有任何的理解，僅僅給我解釋一下那條公理事實(shí)上說了什么。

解答者：

它表達(dá)了這個(gè)意思：正在討論的模型——符合這個(gè)公理的模型——讓形成這樣的類是不可能的：在后繼這個(gè)操作之下是封閉，包含了0但是不包含每一個(gè)東西。在這個(gè)論域中的類不可能是這樣的:0在這個(gè)類中，這個(gè)類中的每一個(gè)東西的后繼也在這個(gè)類中，然而它并不含有每一個(gè)東西。所以，你不能含有一個(gè)不連通的無窮的鏈——（如果存在的話）那將至少存在一個(gè)類，它含有了0以及所有的后繼——后裔，然而并不包含那個(gè)鏈；而且我們有一個(gè)有啟發(fā)性的新公理述說了那個(gè)不可能的。

好奇寶寶：

也許你能夠使用一個(gè)更加直觀的方式來說明？好比說，如果這就是我所信仰的關(guān)于這個(gè)宇宙的事情，那么，什么是我可以期望得到的呢？

解答者：

如果這就是你所信仰的你生在其中的數(shù)學(xué)模型…那么你相信了，不管是你還是其他對(duì)手，抑或是一個(gè)超級(jí)智能體，或者上帝，都不能對(duì)對(duì)象以這種方式來說‘是’或‘非’：當(dāng)你給他們0，他們說‘是’；當(dāng)你給他們?nèi)魏嗡麄冋f‘是’的對(duì)象，他們也對(duì)這個(gè)對(duì)象的后繼說‘是’；然后，存在某個(gè)對(duì)象，他們說‘非’。你相信這絕不能發(fā)生，無論以什么方式。宇宙中的對(duì)象被后繼安裝的這種方式，從不允許那種事情發(fā)生。

好奇寶寶：

啊。如果他們對(duì)42說‘非’，我將回退并且詢問41，然后是40，然后當(dāng)我到了0，我將會(huì)發(fā)現(xiàn)他們對(duì)0說‘非’或者‘他們對(duì)41說了非，然而對(duì)40說了是’。如果我相信帶有無窮公理模式的一階邏輯，我能夠期望得到什么呢？

解答者：

在那種情況，你相信不存在像那樣起作用的靈巧規(guī)定的、緊湊描述的規(guī)則。不過如果你相信那個(gè)二階版本，你相信，沒有人可能像那樣行動(dòng)，即使他們是在隨機(jī)地回答問題，或者把這個(gè)宇宙叉開一個(gè)分支來在不同的宇宙中以不同方式來回答等等。順便注記一下，如果我們有一個(gè)有限的論域[譯注2]，也就是說，我們?nèi)サ袅四莻€(gè)每一個(gè)數(shù)都有一個(gè)后繼的規(guī)則，作為替代假定256是唯一沒有后繼的數(shù)——那么我們就可以在有限時(shí)間之內(nèi)來驗(yàn)證這條公理了。

好奇寶寶：

我明白了。是否存在一個(gè)方法使用一階邏輯去除掉無窮鏈呢？我將發(fā)現(xiàn)那更容易處理一點(diǎn)，即使它剛開始看起來更復(fù)雜。

解答者：

恐怕是沒有的。一種我喜歡看待的方式是：從局部看模型如何這樣的約束，一階邏輯能夠做到，然而只有二階邏輯才能談?wù)撴湣㈩悺⒆鳛橐粋€(gè)整體的模型這些的性質(zhì)。任何一個(gè)數(shù)是否具有后繼是一個(gè)局部性質(zhì)——模型從一個(gè)數(shù)的視角去看是怎樣的，這樣的問題。一個(gè)數(shù)加三是否等于它自己，是一個(gè)這樣的問題：你能夠從任何一個(gè)數(shù)它自己的位置去評(píng)估。一個(gè)數(shù)是否是偶數(shù)，這個(gè)問題你可以通過尋找唯一的一個(gè)數(shù)x使得x x等于那個(gè)數(shù)來回答。但是，當(dāng)你試圖說僅存在唯一的鏈它從0開始，借助于連通、鏈的想法，你在試圖描述非局部的性質(zhì)，這需要指定一個(gè)關(guān)于可能的類的邏輯。

好奇寶寶：

嗯。不過如果所有的局部性質(zhì)都是一樣的，為什么要擔(dān)心整體性質(zhì)呢？在一階邏輯中，任何‘局部’公式它在0以及所有‘自然的’后繼都是是真的，在所有的不連通的鏈它將必須為真… 對(duì)嗎？亦或我弄錯(cuò)了什么？0-鏈之外的所有鏈——所有‘非標(biāo)準(zhǔn)數(shù)’——將像‘自然’數(shù)一樣擁有同樣的性質(zhì)，對(duì)嗎？

解答者：

恐怕不是的。算術(shù)的一階公理不能成功地確定一個(gè)圖靈機(jī)會(huì)停止——是否存在一個(gè)時(shí)刻使得一個(gè)圖靈機(jī)停止。在標(biāo)準(zhǔn)數(shù)中，從我們的視角說某個(gè)圖靈機(jī)‘真的不’停機(jī)——它在第0個(gè)時(shí)鐘滴答不停機(jī)，在第1個(gè)時(shí)鐘滴答不停機(jī)，在第2個(gè)時(shí)鐘滴答不停機(jī)，以及0-鏈上的所有標(biāo)準(zhǔn)后繼。在整數(shù)的非標(biāo)準(zhǔn)模型——擁有其它無窮鏈的模型——在一個(gè)非標(biāo)準(zhǔn)鏈中也許存在一個(gè)位置，圖靈機(jī)走到那里就停止了，而且永遠(yuǎn)停止在哪里。

在這個(gè)新的模型——與一階公理完全兼容，并且不能被它們?nèi)コ簟畬?duì)于任一個(gè)數(shù)t這個(gè)圖靈機(jī)是運(yùn)行的，在t 1它仍然運(yùn)行’不是真的。雖然我們可以把我們的注意力限制在‘自然’數(shù)上，我們可以發(fā)現(xiàn)這個(gè)圖靈機(jī)在0，1，2以及0-鏈的后繼每一個(gè)時(shí)刻都是運(yùn)行的。

好奇寶寶：

OK… 我不是清楚那樣做會(huì)有什么后果？

解答者：

它意味著很多事實(shí)上在標(biāo)準(zhǔn)時(shí)間上從來不停機(jī)的圖靈機(jī)，僅僅使用一階推理,是不能證明不停機(jī)的，因?yàn)樗鼈兊牟煌C(jī)性事實(shí)上是不能從一階公理推論出的。邏輯是關(guān)于那些從前提導(dǎo)出的結(jié)論的，還記得嗎？這意味著你將不能證明——不應(yīng)該證明——這個(gè)圖靈機(jī)停止，只使用一階邏輯的話。

好奇寶寶：

怎么證明不成立呢？我的意思是，那些證明在哪里走不通呢？

解答者：

你將無法得到歸納中的第二步，‘對(duì)于任一個(gè)時(shí)刻t圖靈機(jī)正在運(yùn)行，在t 1時(shí)刻它仍將運(yùn)行’。存在帶有非標(biāo)準(zhǔn)數(shù)t的非標(biāo)準(zhǔn)模型否定了這個(gè)前提條件——在一個(gè)非標(biāo)準(zhǔn)時(shí)間 圖靈機(jī)從運(yùn)行狀態(tài)停止了。我們可以把注意力僅限制在標(biāo)準(zhǔn)數(shù)的話，我們會(huì)發(fā)現(xiàn)那個(gè)圖靈機(jī)在0，1，2等等在運(yùn)行。

、

好奇寶寶：

不過如果一個(gè)圖靈機(jī)事實(shí)上真的停止了，那就存在某個(gè)它停止的時(shí)刻，比如在第97步。

解答者：

是的。不過97存在于算術(shù)的所有的非標(biāo)準(zhǔn)模型，所以我們可以在一階邏輯中證明其存在性。0是一個(gè)數(shù)，每一個(gè)數(shù)有一個(gè)后繼，數(shù)不循環(huán)等等，那將存在97。每一個(gè)非標(biāo)準(zhǔn)模型至少含有標(biāo)準(zhǔn)數(shù)。所以當(dāng)一個(gè)圖靈機(jī)確實(shí)停機(jī)的時(shí)候，你可以在一階算術(shù)中證明它停機(jī)——它推導(dǎo)出自那些前提。那正是你所期待的，假定你可以觀察那個(gè)圖靈機(jī)97步的話。當(dāng)某圖靈機(jī)事實(shí)上停機(jī)的時(shí)候你應(yīng)該可以證明它停止而不需要擔(dān)心無限的未來時(shí)間！當(dāng)它在標(biāo)準(zhǔn)數(shù)中事實(shí)上不停機(jī)的時(shí)候——由于‘非標(biāo)準(zhǔn)停機(jī)時(shí)間’的存在，它就變成了一個(gè)問題。于是，圖靈機(jī)永遠(yuǎn)運(yùn)行這個(gè)結(jié)論也許事實(shí)上不能從一階算術(shù)推導(dǎo)出來，因?yàn)槟憧梢宰駨囊浑A算術(shù)的所有的前提，然而仍有在非標(biāo)準(zhǔn)模型中的某個(gè)位置圖靈機(jī)會(huì)停機(jī)。

好奇寶寶：

所以二階算數(shù)比一階算術(shù)更加強(qiáng)大，就哪些可以從前提推導(dǎo)出來來說？

解答者：

能夠談?wù)撦^少可能的模型這個(gè)能力必然得出那一點(diǎn)。正像已經(jīng)寫到的，“關(guān)于某個(gè)蘋果是真的事情對(duì)于另一個(gè)蘋果不一定是真的；所以，關(guān)于單個(gè)蘋果可說的東西多于關(guān)于這個(gè)世界上所有的蘋果可以說的東西。”如果你能夠把你的論域限制到一個(gè)更狹窄的模型的類上，那就存在更多的可以必然推導(dǎo)出的事實(shí)，因?yàn)槟阏務(wù)摰哪Ｐ驮酱螅P(guān)于它們都真的事實(shí)越少。另外二階算數(shù)比一階算術(shù)證明了更多的定理，它也確實(shí)是真的——比如，它能夠證明一個(gè)能計(jì)算古德斯坦序列的圖靈機(jī)總是到達(dá)0并停機(jī)，赫拉克勒斯總是贏得九頭蛇游戲。不過呢，如果這樣就一般地來說二階邏輯是否事實(shí)上比一階邏輯更加強(qiáng)大，會(huì)遇到一點(diǎn)爭(zhēng)議。

好奇寶寶：

好吧。畢竟，僅僅因?yàn)闆]有人曾經(jīng)發(fā)明一個(gè)一階公式來去除掉所有的非標(biāo)準(zhǔn)數(shù)，并不意味著它永遠(yuǎn)不可能。未來一些聰明的數(shù)學(xué)家也許可以找到一個(gè)方式使得，對(duì)于任一個(gè)數(shù)x，使用加法、乘法、關(guān)于其它單個(gè)的數(shù)是否存在這些來對(duì)它僅作局部的事情，這個(gè)方法可以告訴我們那個(gè)數(shù)是在0-鏈上，亦或在某個(gè)雙向無窮的鏈上。它將簡(jiǎn)單得就像：

(a=b*c)

解答者：

不。那不會(huì)發(fā)生。

好奇寶寶：

不過，也許，你能否找到一些完全不同的創(chuàng)新的方式，只用一階公理得到全部都是標(biāo)準(zhǔn)自然數(shù)的模型。

解答者：

不可能。

好奇寶寶：

嗯…你是如何準(zhǔn)確地知道那一點(diǎn)的？我的意思是，當(dāng)你參加一個(gè)比賽，作為比賽選手的一條原則就是當(dāng)某事看起來不可能的時(shí)候，你不要放棄。我不能明白如何使用一階公式來檢查無窮的鏈。不過，先前我不能認(rèn)為你可以去除有限圈，一旦你講解了，它就顯得非常簡(jiǎn)單。畢竟，關(guān)于‘不可能’這個(gè)詞存在兩種不同的用法，一種直接用已有知識(shí)表明了某事不能實(shí)現(xiàn)，也就是說哪怕你是一個(gè)超級(jí)智能體，也不可能找一種做法來達(dá)成這個(gè)目標(biāo)。這種情況，你需要利用已知知識(shí)給出一個(gè)確定、完整的結(jié)果，從而你可以否定每一個(gè)可能的成功途徑。還有另外一種，‘不可能’一詞更加通常的用法：你思考了五秒鐘沒有發(fā)現(xiàn)實(shí)現(xiàn)它的方法，然后就說”不可能“。一般在對(duì)知識(shí)了解有限，那個(gè)問題又看起來有些神秘主義傾向會(huì)這樣。

解答者：

是的。使用一階公式來去除掉雙向無窮鏈，是第一種類型的不可能。我們知道它永遠(yuǎn)不可能實(shí)現(xiàn)。

好奇寶寶：

嗯，我知道。好吧，你有什么觀點(diǎn)，如何說明你的觀點(diǎn)？能用你明確的知識(shí)正面回答為什么‘不可能’嗎？別用這種神秘兮兮的方式強(qiáng)行灌輸？

解答者：

下一次，下一次我們?cè)賮砗煤弥v講。

譯者注：

[1]非直謂的(impredicative)

[2]原文universe既可以翻譯為宇宙，也可以在某些情況下翻譯為“論域”。有些情況下，難以抉擇，或者本身就是雙關(guān)。請(qǐng)讀者自己記住這一點(diǎn)。

關(guān)注 哆嗒數(shù)學(xué)網(wǎng) 每天獲得更多數(shù)學(xué)趣文