把變量“把變量 x 用自指代換就稱作對角化”用自指代換就稱作對角化。
無法證明把“無法證明把 x 對角化了的語句”對角化了的語句。
——《沒有書名為〈沒有書名為的書〉的書》
7.1 數列的數列
7.1.1 可數集
“學長，我找你好久了！有東西給你！”
“嗯？”我停下秒錶。
“啊，對不起！你在計時啊！”
“沒事……”我把思緒移回這個世界，“呼 —— ”地舒了一口氣。在解數學題時，我會進入異世界。現實中的自己身處於哪個時代、哪顆星球、哪個國家……全都失去了意義。
——現在是放學後，這裡是圖書室。
季節是冬季，但已略有春意。已是二月末了，下個月就是畢業典禮跟結課典禮 1，還有春假。
1日本的小學和初高中在學期末還舉行結課典禮。——譯者注
到了四月，我跟米爾嘉就升高三了，泰朵拉就升高二了。時間過得好快啊。
“……沒事，我已經把秒錶停了。什麼東西啊？”
“您有黑貓泰朵拉的快遞，是村木老師的卡片！”
“……謝謝。是什麼題？”
問題 7-1
證明實數集
不是可數集。
“啊，這題我知道，是數學讀物裡常出現的題。”
“誒？這題這麼有名嗎？”
“解這題要用到康托爾的對角論證法 2——需要我解釋嗎？”
2即 Cantor's Diagonal Argument，又稱對角線證明等。——譯者注
“……嗯。如果不妨礙你的話，還請解釋一下。”
泰朵拉說著，坐到了我左邊的座位上。
“解釋的話，一下子就能解釋完。我們先不說這個，你明白這道題的含義嗎？”
“……除了可數集這個詞以外，我應該都明白。”
“可數集指的是‘能用自然數給所有元素編號的集合’。”
可數集
可數集指的是能用自然數給所有元素編號的集合。
“用自然數來編號……”
“比如說，有限集都是可數集 3 對吧？這是因為，如果元素數量有限，那麼我們就能給所有元素都編上號。”
3也有一些學派主張有限集不屬於可數集。
“瞭解。”
“至於無限集的示例嘛，比如說，我們假設存在一個下面這樣的整數集 
。
是可數集。也就是說，我們可以用自然數給整數編號。來動手試試吧。用自然數 1 給整數 0 編號，然後依次用 2 給 +1 編號，用 3 給 -1 編號，用 4 給 +2 編號……”
“嗯……”
“這麼寫的話，應該更容易理解吧。”
“就是輪流加上正負號……對吧？”
“嗯。用哪種方法都行，重要的是給所有整數都編上‘單獨的編號’。因為所有的整數都能用自然數來編號，所以我們可以說，整數集 是可數集。用英語說就是 Countable Set。”
“原來如此。Countable，可數的，就是能夠 Count 的集合呀。”
“嗯，就是這樣。另外，再比如說有理數集 
，它也是可數集哦。因為，像下面這麼排的話……
我們就能順籐摸瓜，找到所有大於等於 0 的有理數。接下來，只要跟上面處理整數時一樣，輪流加上正負號即可。
不過，往細了說呢，當出現像 
跟 
這樣約分後相等的數時，還必須跳過後出現的數。”
“有理數集也是 Countable Set 啊。”泰朵拉點了點頭，又歪了歪頭，“可是……能拿自然數來編號，不是理所當然的麼。因為自然數是 1, 2, 3, ...，有無數個呀。”
“泰朵拉，你是不是想說‘因為自然數有無數個，所以當然能用它們給無限集合的元素來編號’？可是啊，卡片上寫著呢，實數集 不是可數集。也就是說，就算動用無數個自然數，也不可能給所有的實數都編上號。”
“實數集 不是可數集……？可是學長，如果有那種沒有編號的實數，只要每次遇見這種實數時把它單拿出來編號不就行了！”泰朵拉揚起雙手。
“不行不行，這樣是搞不定的。”
“為什麼？”
“因為這個方法不能保證給所有的實數都編上號。”
“可……可是，就算我說的方法不行，也許別人能想出個好方法呢？給有理數編號就辦得到，給實數編號卻絕對辦不到？怎麼就能這麼說呢？”
“證明就是為此而存在的，泰朵拉。這就是這次要討論的問題。”
7.1.2 對角論證法
問題 7-1
證明實數集
為了使用對角論證法，我們換個角度理解一下這道題。把“給所有實數編號”改成“給滿足 0 < x < 1 的實數編號”吧。
為什麼要改成這樣呢？這是因為，能給滿足 0 < x < 1 的實數編號，就相當於能給所有實數編號。
請看下圖。
由上圖可知，如果我們在 x 軸上的 0 < x < 1 這個範圍內選定一個實數 a，則 y 軸上會出現一個對應的實數 b。反過來，如果我們在 y 軸上選定一點 b，則 x 軸上會出現一個滿足 0 < x < 1 的實數 a。滿足 0 < x < 1 的實數跟所有實數之間的這種關係是一一對應的，不會出現遺漏，也不會重複。
因此，給滿足 0 < x < 1 的所有實數編號，就相當於給所有實數編號。
問題 7-1a（問題 7-1 的另一個說法）
證明由滿足 0 < x < 1 的所有實數構成的集合不是可數集。
那麼，接下來介紹一下康托爾的對角論證法。
在這裡我們使用反證法。
在反證法中，我們要先假設一個想證明的命題的否定形式，然後推導出矛盾。現在我們想證明的命題是“由滿足 0 < x < 1 的所有實數構成的集合不是可數集”，因此我們可以假設這樣一個該命題的否定形式。
反證法中的假設：由滿足 0 < x < 1 的所有實數構成的集合是可數集。
我們的目標是從以上假設出發，也就是通過“能用自然數給滿足 0 < x < 1 的所有實數編號”，推導出矛盾。
既然滿足 0 < x < 1 的所有實數都有編號，那麼這個範圍內的所有實數就都能用 An 來表示。n 是我們編給實數的編號。
我再寫得具體點吧。比如，An 可能是下面這樣。
在這裡，我們試著把“以‘0.’開頭的數”寫作一般的形式。
下標有兩個字符，看起來挺費勁的，不過你應該明白吧？ an,1 表示的是實數 An 的小數點後的第 1 位數字。an,2 是小數點後第 2 位數字，an,3 是小數點後第 3 位……以此類推。一般來說，an,k 表示的是實數 An 的小數點後的第 k 位數字。
例如，以 A5 = 0.31415 ... 為例，a5,k 就會變成下面這樣。
改寫成下面這樣會更一目瞭然吧。
然而，就像 中存在 0.1999 ... = 0.2000 ... 這樣，這裡同樣有一些數存在兩種表示方式。為了統一表示方式，我們不把 9 無限寫下去。啊，還有，因為數滿足 0 < x < 1，所以也要排除 0.000 ... 這種寫法。
接下來，我們把 an,k 列成一個像下圖這樣的表格，各行表示的是 An。
滿足 0 < x < 1 的實數都可以用 An 來表示。換句話說，這個表格裡寫的就是滿足 0 < x < 1 的所有實數。我們來看一下這個表格的對角線。
把對角線上的數列挑出來，排列如下。
根據這個數列 
，可以構成下面這個數列 
。
也就是說，我們可以規定，若 an,n 是偶數，則 bn = 1；反過來，若 an,n 是奇數，則 bn = 2。這樣一來，對於所有的自然數 n，以下式子都成立。
接下來，我們如下定義實數 B。
用具體例子來說會好些吧。
首先，從表格裡挑出位於對角線上的數字。
數列 如下。
數列 {bn} 如下。若 an,n 為偶數，則令 bn = 1；若 an,n 為奇數，則令 bn = 2。
這樣一來，我們就得到了實數 B。
此外，0 < B < 1 在任何時候都成立對吧？也就是說，剛剛那個寫著“滿足 0 < x < 1 的所有實數”的表格裡應該有這個實數 B！此處很重要！我們假設實數 B 在表格的第 m 行。那麼，以下式子成立。
接下來，我們把表格的第 m 行和第 m 列挑出來看看。
注意看這張表格的第 m 行和第 m 列的交匯處，可知以下式子成立。這裡拿了 Am，也就是 B 的小數點後的第 m 位數字來與 bm 作比較。
然而，如果我們在此回憶一下 B 是怎麼來的，就會發現：對於所有的自然數 n，
都成立。這是因為，bn 是我們以此為條件刻意構成的。既然對於所有的自然數 n， 都成立，那麼對於某個特定的自然數 m，以下式子也成立。
你看，出現矛盾了吧？
與 相矛盾
因此，根據反證法可知，由滿足 0 < x < 1 的所有實數構成的集合不是可數集。
證明完畢。
解答 7-1a
採用反證法。
假設實數的集合
是可數集。
集合
的元素都可以像下面這樣來表示。
如下定義實數 B。
但是，bn 要像下面這樣來定義。
根據 bn 的定義可知，對於任意自然數，
因為實數 B 是集合
此時再看實數 B 的小數點後的第 m 位數字，就會發現
根據上面第 4 條可知，
在此，第 6 條與第 7 條相矛盾。
根據反證法，集合
這裡也同時回答一下泰朵拉你拿來的那張“快遞”卡片上的問題吧。
由滿足 0 < x < 1 的所有實數構成的集合，跟實數集 是一一對應的關係。因為由滿足 0 < x < 1 的所有實數構成的集合不是可數集，所以實數集 也不是可數集。
解答 7-1
“由滿足 0 < x < 1 的所有實數構成的集合”跟“實數集
這樣你就能理解了吧？
◎ ◎ ◎
“這樣你就能理解了吧？”我說道。
活力少女在沉思默想。沒過多久，她舉起了右手。
“學長，我們把這個方法叫作對角論證法，是因為我們關注的是表格的對角線，對吧？”
“沒錯。不過表格是無限大的，所以我們並不能看到右下角的對角線。”
“我差不多明白剛才是在幹什麼了。不過我想問個問題。”
“什麼問題？”
“要是實數 B 不在表格裡，我們能把它追加到表格裡嗎？”
“不行，如果 B 原本就不在表格裡，就會產生矛盾，所以 B 不能不在表格裡。就算我們把它追加到了表格裡……因為追加後得到的是一個新的表格，所以如果用這個新的表格來像上面那樣討論，我們就還需要定義一個新表格中沒有的實數 C。”
“啊！原來如此。”
“嗯。”
“學長……學長你，為什麼能一下子就回答出我的問題呢？”
“這個嘛，因為我很瞭解對角論證法……”
“是麼？”清脆的聲音從我們背後傳來。
“呀！”泰朵拉叫道。
我回過頭，發現米爾嘉正站在我們身後。
7.1.3 挑戰：給實數編號
“完全沒感覺到你過來了。”我說道。
“別說這些沒用的，剛剛你說自己‘很瞭解’對角論證法？”
我看著雙手叉腰的米爾嘉，不由得很緊張。
“是我說的……”我有點兒不鎮定。
“村木老師簡直就是千里眼啊。”米爾嘉說。
“什麼意思？”
“師曰：‘如果他在給泰朵拉講完以後，說自己很瞭解對角論證法的話，就給他看這張卡片’。”
米爾嘉拿出一張卡片放在桌子上，迅速在我右邊坐下。
問題 7-2（挑戰：給實數編號）
以下關於“給實數編號”的討論是否正確？
給以“0.”開頭的數編號。小數點後第 1 位數字只有 10 種情況 4，因此，對於小數點後只有 1 位數字的數，我們可以無一遺漏地全都編上號。而對於小數點後第 1 位數字的 10 種情況下的每一個數，其小數點後第 2 位數字也都只有 10 種情況。因此，對於小數點後只有 2 位數字的數，我們也可以無一遺漏地全都編上號。重複以上步驟，不管以“0.”開頭的數的位數增加到多大，我們都可以無一遺漏地為其編上號。因此，由以“0.”開頭的所有數構成的集合是可數集。
4即 0～9 這 10 種情況。——譯者注
“我不理解什麼意思。”泰朵拉探頭看著卡片。
“如果能用自然數給某個集合裡所有的元素都編上號，該集合就是可數集。”米爾嘉不緊不慢地解釋道，“根據村木老師給出的這個‘給實數編號’來看，由滿足 0 < x < 1 的所有實數構成的集合是可數集。但是，剛剛你們應該已經證明了，該集合不是可數集。”
“啊……是這麼回事兒。——不對，這個不正確！”
“問題是哪裡不正確。”米爾嘉說道。
“這個……”我說，“在小數點後面每一個數位上可能出現的數字是 0～9 這 10 個數字中的一個。也就是說，如果我們不胡亂給實數編號，而是從位數少的開始依次編號，就能都編上號？不不，應該不是這樣……”
我沉思。持續增加位數的話……
- 0.0, 0.1, 0.2, ... , 0.9（10 個）
- 0.00, 0.01, 0.02, ... , 0.99（100 個）
- 0.000, 0.001, 0.002, ... , 0.999（1000 個）
- 0.000, 0.0001, 0.0002, ... , 0.9999（10000 個）
- ……
“嗯。這麼排列的話，會不會有遺漏呢……每一個數位上出現的數字肯定只有 10 種情況。我們可以無限增加位數，因此……咦？”
“你的對角論證法是不是錯了啊？每一個數位上出現的數字是有限的，所以要是分門別類來編號的話，就能說 0 < x < 1 是可數集了哦。”
米爾嘉用認真的語氣說道。可是，我卻看到她眼裡滿是笑意。她在跟我開玩笑。
泰朵拉舉起了手。
“那個……米爾嘉學姐，請問，我能提個問題嗎？”
“這個是元問題 5。”
5“元”字出於英語的 Meta，元問題就是在現有問題上延伸出來的問題，比現有問題討論的程度更深一些。——譯者注
“啊……是呀。我這是個關於問題的問題呢。”泰朵拉微笑，“採用這個方法的話，0 也會被編號。這樣一來，實數就不在 0 < x < 1 這個範圍內了。而且，像 0.01、0.010 和 0.0100 這樣的實數是相等的，但可能會被重複計數。這就不準確了吧？”
“提得好，但這不是問題。如果在意這些，就跳過那些不在範圍內的實數，還有已經編完號的實數即可。你們之前討論有理數的時候，應該也跳過了相等的數。”米爾嘉回答道。
“啊，這……也是呢。”泰朵拉說道。
我混亂了。
這道題，肯定是能一下子答出來的題。
我原本以為，自己已經把對角論證法這個數學讀物上常出現的知識理解得很透徹了。可是，我卻沒能找出“給實數編號”中的錯誤。
泰朵拉也很認真地在思考。我可不能輸給她。
可是，位數應該能無限增加的啊……
嗯？
……關鍵在於這裡麼？
不管位數多大都能編上號 —— 話雖這麼說，可是這裡的位數不是有限的嗎？比如說 0.333 ... 這個數，這是一個無限小數，位數會無限增多。而村木老師的方法是能給那些位數有限的小數編上號，而不能給無限小數編上號！
“我明白了。用這個方法只能給位數有限的小數編號。”
“沒錯。”
“啊啊啊啊！別說出來呀！”泰朵拉喊道。
“實數（或者有理數）中包含無限小數。”我說道，“當然，在 0 < x < 1 這個範圍裡也存在這種小數，例如 
。
或者，用圓周率 π 除以 10 也可得出這種小數。
在村木老師出的‘給實數編號’這道題裡，不管小數的位數有多少，我們都能給它編上號。但是，這只限於位數有限的情況。當位數無限時，就不能用這個方法了。因為用於編號的自然數會變得無限大。而自然數里沒有無限大的數，所以我們不能用自然數給 0.333 ... 編號。”
米爾嘉輕輕點頭，對我的話予以回應。
解答 7-2（挑戰：給實數編號）
討論不正確。
我贏了老師的“挑戰”，不由得露出了笑容。
“師曰……”黑髮才女酷酷地繼續說道，“‘他要是馬上發現了這個說法的破綻，因而得意忘形的話，你就給他看這張卡片的背面’。”
“卡片的背面？”
我把桌子上的卡片翻了過來。
背面還寫著一道題。
7.1.4 挑戰：有理數和對角論證法
問題 7-3（挑戰：有理數和對角論證法）
用對角論證法證明“實數集不是可數集”後，把其中所有的“實數”換成“有理數”。這樣一來，我們就能證明“有理數集不是可數集”。該證明錯在哪裡？
“唔……”我集中精神想著。
“這……是什麼問題啊？”泰朵拉問道。
“把剛剛用對角論證法進行的證明裡的……”米爾嘉開口回答，“‘實數’一詞統統代換為‘有理數’。也就是說，假設 An 表示有理數，列一個 An 的表格，表格裡寫有在 0 < x < 1 這個範圍內的全部有理數。然後挑出對角線上的數字，構成一個不存在於表格中的有理數 B。這樣一來，就證明了‘有理數集不是可數集’。然而，有理數集應該是可數集。那麼，到底是哪兒出錯了呢 —— 這道題就是這個意思。”
米爾嘉目光中帶著幾分頑皮，開心地解說道。
不不，現在不是盯著人家女生的臉看的時候。……確實，這樣一來就證明了有理數集不是可數集。這……不好辦呀。
“泰朵拉，你能答嗎？”米爾嘉問道。
“不，我不會。”泰朵拉搖搖頭，“我只知道，學長的對角論證法裡，某個地方對於‘實數’成立，而對於‘有理數’不成立……”
“這說法有前途。”米爾嘉點點頭。
“原來如此……應該找出實數跟有理數本質上的差異啊。”
實數跟有理數的差異是什麼呢？實數的一部分是有理數，有理數可以用分數來表示。不過，現在是用小數來表示的。用小數來表示的話……啊！
“我明白了。”
“真的？”
“嗯。在對角論證法的末尾部分，我們斜著選了一個 
，對吧？然而，我們並不能保證由此構成的 B‘會是有理數’。用小數來表示有理數的話，數的規律就會陷入循環，也就是循環小數。例如， 就是像 0.333 ... 這樣循環 3，
就是像 0.142857142857142857 ... 這樣循環 142857。我倒是想說‘數 B 應該會出現在表格裡’，然而無法保證‘根據有理數表格構成的數 B 會是循環小數’。也就是說，數 B 不一定會是有理數。因此，村木老師的卡片上寫的那種把實數代換成有理數的證明並不正確。”
“很好。”米爾嘉點頭。
解答 7-3（挑戰：有理數和對角論證法）
因為構成的數 B 不一定是有理數，所以不能使用對角論證法。
“這樣啊……”我自言自語般說道，“重要的是，就算是像對角論證法這種著名的論證方法，也需要好好確認自己是否已經完全理解了它的含義啊。看來，‘我聽說過’‘我在書上看到過’跟‘我已經完全理解了’相比，差距還是相當大的呀。”
“學長也是這樣想呀。”泰朵拉回應道，“那個……我說一下別的哈。剛剛的證明裡出現了反證法吧？”
“嗯，是啊。”我答道。
“反證法裡的‘矛盾’……”泰朵拉繼續說道，“一說到矛盾，我就有一種特別混亂，理不清思路的感覺。但是，我現在覺得，矛盾或許是一個步驟，這個步驟包含於一種更純粹的思路之中。矛盾只不過是一個數學術語……”
“否定也是如此。”米爾嘉說道。
“啊，是呢！平常我們用‘否定’這個詞，就很有負面、消極的感覺，而在數學裡就完全沒有這種感情色彩，可以毫無顧忌地否定。”
“根據辭典裡的含義來看，‘否定’可能也是一個很容易令人誤解的術語呢。”我說道。
“……話雖這麼說，數學家還是很了不起的。”泰朵拉說道，“皮亞諾的公理、戴德金的無限定義，還有魏爾斯特拉斯的 
語言、康托爾的對角論證法……數學家把線索留給了我們，讓我們去發現這些既不可思議又美麗有趣的事物。他們簡直就像弄丟了玻璃鞋的白雪公主。”
“確實……不過那可不是白雪公主，是灰姑娘。”我說道。
“哎呀！是啊！”泰朵拉紅了臉。
7.2 形式系統的形式系統
7.2.1 相容性和完備性
卡片的問題告一段落，我們稍稍歇了一會。
米爾嘉用雙手在胸前比劃著一個小小的鳥籠，若有所思。她的手指也是彈鋼琴的手指，不過跟盈盈的還不一樣。她的手指纖長，形狀秀美。
“來聊聊算術的形式系統吧。”她突然來了這麼一句。
“啊，就是之前那個‘裝作不知道的遊戲’吧。”泰朵拉說道。
“略有不同。”米爾嘉回答道，“之前是‘命題邏輯的形式系統’，這次是‘算術的形式系統’。”
“形式系統有這麼多種嗎？”
“有無數種，這要看定義。”
“哦哦……”
“你會這麼問，就是說你已經忘記了形式系統吧？”
“這……這個，嗯，對不起。”泰朵拉答道。
“唔……那麼，我們再來簡單複習一遍形式系統吧。”米爾嘉說道，“形式系統中定義了‘邏輯公式’。邏輯公式只是符號的有限序列 —— 我們先不考慮這句話的含義。然後，選出幾個被稱為‘公理’的邏輯公式。另外，為了由邏輯公式推導出邏輯公式，還要準備‘推理規則’。”
她拿起我的筆記本和自動鉛筆，寫下了“邏輯公式”以及“公理和推理規則”。
“從公理開始，用推理規則推導出邏輯公式，然後把邏輯公式加以排列，就能得到邏輯公式的有限序列。這種邏輯公式的有限序列就叫作‘證明’。在證明的結尾處出現的邏輯公式叫作‘定理’。”
米爾嘉又在筆記本上寫下了“證明和定理”。
“喏，泰朵拉，你想起來了沒？”
“嗯……我想起來了。形式系統中的證明指的不是數學意義上的證明，而是作為邏輯公式的有限序列來定義的‘形式證明’。學姐之前還列了五個邏輯公式來當 
這個邏輯公式的形式證明呢……我給忘掉了，對不起。”
“用什麼樣的符號序列來當邏輯公式，用什麼樣的邏輯公式來當公理，準備什麼樣的推理規則……”這時米爾嘉將雙臂大大伸展開來，“我們可以根據這些條件來構建各種各樣的形式系統。我前一陣提到過的命題邏輯的形式系統算是其中比較簡單的。玩起來很有趣，但是表現力卻很低。”
“表現力？”我不解。
“比方說， 這個式子可以用命題邏輯的形式系統來寫。然而，下面這個式子就不行。”
我跟泰朵拉望著米爾嘉寫的式子，看了好一會兒。
“米爾嘉學姐，這個式子的意思是？”泰朵拉問道。
“我明白了。”我說道，“它的意思是‘17 是質數’。你看，它強調的是，不管把哪兩個數代入 m 跟 n 裡，乘積都不等於 17。”
“m < 17 和 n < 17 的部分呢？”泰朵拉問道。
“如果沒有這部分，就能寫成 1 × 17 的乘積形式了。”我回答道。
“啊……確實。我把質數的定義給忘了！”
“你們還真是喜歡思考含義啊。”米爾嘉冷冷地說道。
“啊！”對了！不該思考含義的。
“可是……”泰朵拉說道，“米爾嘉學姐在寫這個邏輯公式的時候，是想讓我們以為‘17 是質數’的吧。從形式系統的角度來說，可能確實不應該考慮含義。但是，要是進行正確的解釋，這個式子不也是為真……嗎？”
“我想說的就是這個。”米爾嘉說道，“我們需要注意泰朵拉剛才所說的‘正確的解釋’。對解釋進行思考是歸在數理邏輯裡的模型論這個範疇裡的。確實，一旦我們定義了解釋，也就給形式系統賦予了含義。但是，正確的解釋不單單只有一個。對於一個形式系統，我們可以想到很多解釋。解釋不同，形式系統的含義也會發生變化。然而，還是存在常用的標準解釋的。”
“……”
“比如說，你們剛剛將 m 跟 n 默認為自然數，把 m 跟 n 認定成自然數，把‘×’認定成自然數的乘積，把‘≠’解釋成表示不相等的符號。的確，這麼解釋的話，那個式子表示的就是‘17 是質數’這個命題。但是，如果 m 和 n 是實數呢？這樣一來，那個式子表示的意思就不是‘17 是質數’了。所以，要給形式系統賦予含義時，我們需要切實定義解釋。”
“原來如此……”我跟泰朵拉一起點頭。
“不過，實際上泰朵拉說的沒錯，我就是想讓你們以為這個式子表示的是‘17 是質數’……”米爾嘉俏皮地擠了擠眼說道，“我們回到正題。在命題邏輯的形式系統中，以下邏輯公式是寫不出來的。
這是因為，命題邏輯的形式系統裡缺少以下內容。
-
沒有
這樣的符號。 - 沒有 × 這樣用於計算自然數的符號。
- 沒有 < 和 ≠ 這樣用於表示自然數間關係的符號。
- 沒有 m 和 n 這樣用於表示自然數的變量。
- 沒有 17 這樣用於表示自然數的常數。
如果想要從形式上表示算術這種在自然數的基礎上進行加法或乘法運算的簡單的數學，就需要把上面這些缺少的部分補上。”
“把缺少的部分補上……指的是什麼呢？”
“導入缺少的符號、變量、常數等，定義公理和推理規則。”
“這個……”泰朵拉一臉快要哭出來的樣子，“可是，要是能這麼隨便干的話，感覺就收不了場了……不管是誰都能隨便創造數學，這樣就會出現一波又一波亂七八糟的數學……”
“並非如此。”米爾嘉說道，“雖然誰都能創造形式系統，但並不會收不了場。這一點跟誰都能創造音樂，但優美的音樂並不多很像。因為還有些重要性質是形式系統應該滿足的。”
“形式系統的……性質？”泰朵拉眨了幾下眼。
“例如相容性 6。形式系統需要相容。”
6又稱無矛盾性、協調性或者一致性，指的是邏輯上的一致，就是在一個邏輯體系下永遠不可能同時推理出一個命題 P 和其否命題非 P 同時成立。——編者注
“相容性……也就是說，跟矛盾有關？”
“當然。”米爾嘉說道，“形式系統存在‘矛盾’指的是對於某個邏輯公式 A，我們能夠證明 A 和 
（非 A）兩者都成立。也就是說，如果存在邏輯公式 A，滿足 A 和 都有形式證明，那麼這個形式系統就存在矛盾。”
存在矛盾的形式系統
對於形式系統中的某個邏輯公式 A，
能夠證明 A 和
我們就說，這個形式系統存在矛盾。
“那個……米爾嘉，”我插了句嘴，“就是說，我們能從公理出發，沿著推理規則一路摸索到達 A 和 ？”
“你理解得很對。”米爾嘉回答道，“在形式系統包含的大量邏輯公式裡，哪怕存在一個能證明 A 和 兩者都成立的邏輯公式 A，我們就說這個形式系統‘存在矛盾’。相應地，如果完全不存在這樣的邏輯公式 A，我們就說這個形式系統‘相容’。”
相容的形式系統
對於形式系統中的任意邏輯公式 A，
無法證明 A 和
我們就說，這個形式系統相容。
“原來如此。”我想。形式系統中連矛盾這個概念都不用真假來定義啊。通過能不能證明來定義矛盾……原來如此。
泰朵拉想了一會兒，突然大聲說道：
“相容的話，我們就能證明 A 和 有一方肯定成立吧！”
“這可說錯了。”米爾嘉立馬否定了泰朵拉的說法。
“誒？誒誒誒誒？”
“‘無法證明 A 和 兩者都成立’這個性質即相容性。泰朵拉，你好好想想下面這兩種說法之間的差別。”
-
無法證明 A 和 兩者都成立。
-
能證明 A 和 有一方肯定成立。
“不……不對嗎？”泰朵拉雙手放在頭上思考著。
“你忘了‘兩者都無法成立’的情況。”米爾嘉說道。
“啊！……誒？ A 和 兩者都不成立？”
“對，雖然形式系統相容，但不一定就能證明 A 和 有一方肯定成立，也存在相容且 A 和 兩者都無法成立的情況。然而，在包含自由變量 7 的邏輯公式中也有很多無法證明的東西。現在我們關注的不是一般意義上的邏輯公式的可證明性，而是不包含自由變量的邏輯公式 —— 人們將其稱為語句 8 ——的可證明性。”
7也稱自由變元。——譯者注
8也稱句子（Sentence）、閉公式（Closed Formula）。——譯者注
“自由變量……那是什麼？”泰朵拉問道。
“自由變量指的是不受 或 
束縛的變量。例如，在下面的邏輯公式 1 中，出現了三次 x，x 就是自由變量。因為邏輯公式 1 包含自由變量，所以它不是語句。”
邏輯公式 1：不是語句
“而下面這個邏輯公式 2 不包含自由變量，所以它是語句。”
邏輯公式 2：是語句
“嗯……”
“話說，米爾嘉，”我插嘴道，“如果換成算術的形式系統，這個邏輯公式 1 表示的就是‘x 是質數’這個謂詞，邏輯公式 2 表示的就是‘17 是質數’這個命題吧？”
“嗯，你這麼想也行。”米爾嘉點頭，“總之，語句指的是不包含自由變量的邏輯公式。好了，我們回到正題吧。假設對於形式系統中的語句 A，A 和 兩者都無法證明。此時，A 就叫作不可判定的語句。還有，我們稱擁有不可判定的語句的形式系統不完備，稱非不完備的形式系統完備。”
我看著米爾嘉，不由得提高了說話聲。
“不完備？難道是哥德爾的那個……”
“對，就是不完備定理的那個‘不完備’。”米爾嘉說道。
不完備的形式系統
對於形式系統中的某個語句 A，
A 和
我們就說，這個形式系統不完備。
完備的形式系統
對於形式系統中的任意語句 A，
能夠證明 A 和
我們就說，這個形式系統完備。
“我們假設 A 是任意一個語句。泰朵拉剛才說的‘能證明 A 和 有一方肯定成立’的性質，也就是形式系統‘相容且完備’的性質。這性質非常妙。相容且完備 —— 數學家希爾伯特在形式系統上追求的正是這個性質。不過……”
隨後，米爾嘉停頓了一下說道：
“哥德爾不完備定理粉碎了這個性質。”
7.2.2 哥德爾不完備定理
“哥德爾不完備定理是什麼？”泰朵拉問道。“
關於形式系統的定理。”米爾嘉答道，“哥德爾不完備定理包括兩條定理，分別是第一不完備定理和第二不完備定理。第一不完備定理的內容如下。”
哥德爾第一不完備定理
滿足某個條件的形式系統是不完備的。
“我們還可以用‘不完備’的定義來換一種說法。”
哥德爾第一不完備定理（換言之）
在滿足某個條件的形式系統中，存在滿足以下兩個條件的語句 A。
- 無法證明 A 成立。
- 無法證明
“A 和非 A 都無法證明……”泰朵拉不安地自言自語。
“剛剛這個‘無法證明’說得比較簡單，不過其含義顯然就是‘不存在形式證明’。在理解不完備定理時，必須意識到‘數學上的證明’和‘形式證明’這兩者的差別。‘無法證明’體現為‘不存在形式證明’。我們再用‘形式證明’這種表述，換個說法來描述一下第一不完備定理吧。”
哥德爾第一不完備定理（再換言之）
在滿足某個條件的形式系統中，存在滿足以下兩個條件的語句 A。
該形式系統中不存在 A 的形式證明。
該形式系統中不存在
“還有第二不完備定理嗎？”泰朵拉問道。
“有。第二不完備定理是關於相容性的定理。不過，現在就講它的話，你會消化不了的。我們就留到下次再講吧。”米爾嘉說道。
“嗯，很可能。我已經快消化不了了……”
“先不說這個，我們來談談哥德爾當時證明第一不完備定理時用的技巧吧。這是一場往返於兩個世界的旅行。”
7.2.3 算術
米爾嘉緩緩地來回看著我跟泰朵拉。
“人們把進行自然數的加法、乘法等運算的系統叫作‘算術’。如果能構建這個形式系統，也就是‘算術的形式系統’，就能在形式上定義自然數的加法、乘法等運算。而且，順利的話，或許還能用‘算術的形式系統中的語句’來表示‘2 是質數’‘5 的 17 次方等於 762939453125’這種‘算術的命題’。那麼……”
沉默。
米爾嘉足足停了好一會兒才開口，看上去似乎很樂在其中。
“我們再試著好好思考一下形式系統這東西。形式系統中最根本的是符號。如果是命題邏輯的形式系統，就是用 
、
、
和 
這些符號排列構成邏輯公式。如果是算術的形式系統，則是用 
、
、
、
、
和 
等符號排列構成邏輯公式。話說回來，這些符號不一定非得寫成這樣。符號這東西，只要互相能夠區別開來，用什麼都無所謂……是吧？”
她突然上揚了句尾的語調問道。我們不置可否地點點頭。
米爾嘉到底要把我們帶向何方呢？
她繼續講道：
“……因此，我們拿自然數來當用於構建算術的形式系統的符號吧。舉個例子，我們就拿 3 替代 
，拿 5 替代 
，拿 17 替代 
，拿 7 替代 
，拿 19 替代 
，拿 9 替代 
。”
“為……為什麼 
就是 3 了呢？”泰朵拉有些焦慮。
“只是舉例子而已。現在只是隨便分配一下。”米爾嘉微笑著回應道。
“為什麼要拿自然數當符號來用？”我問道。
“因為自然數能用算術來處理。”
“能用算術來處理？”
“你們知道我打算幹什麼嗎？”
我們使勁搖頭。
米爾嘉推了一下眼鏡。
“唔……不明白是吧？”
形式系統
——能用符號來寫；
符號
——能用自然數來表示；
自然數
——能用算術來處理。
“把這三個條件合起來，自然而然就能想到用‘算術’來處理‘形式系統’了。不過，我們能自然而然就想到，可能是因為我們身處於哥德爾之後的時代。”
米爾嘉的話讓我啞口無言。
到底該說些什麼好呢？
泰朵拉在我身旁抱著頭呻吟。
“嗚嗚嗚嗚，好難啊，好複雜呀……”
7.2.4 形式系統的形式系統
米爾嘉趁著興頭繼續“上課”。
◎ ◎ ◎
下面來說說哥德爾數吧。
我們分別用自然數 3、5、17、7、19、9 來表示符號 
、
、
、
、
、
。注意，這裡只是舉個例子而已。
因為邏輯公式 
可以看作符號的序列，所以我們也可以用自然數的序列（3, 5, 17, 7, 19, 9）表示邏輯公式。
而且，用質數指數記數法還能把“自然數的序列”統合成“一個自然數”。例如，假設有個像下面這樣的自然數的序列。
當我們想把這個自然數的序列統合成一個自然數時，就需要另外準備一個把質數從小到大排列的序列（2, 3, 5, 7, 11, 13, .. .）。然後，把剛剛的自然數的序列 
一個個挪到質數的指數位置上去，並取整體的乘積。這樣一來，我們就能像下面這樣構建出一個很大的自然數。
如此，我們就能根據所有的邏輯公式來構建“單獨的編號”了。這裡說的“單獨的編號”就叫作哥德爾數。
拿剛剛的例子來講的話，
這個邏輯公式的哥德爾數就是 792179871410815710171884926990984804119873046875000。
跟邏輯公式一樣，形式證明也能定義哥德爾數。形式證明是“邏輯公式的有限序列”。因為用“自然數的有限序列”能表示邏輯公式，所以用“‘自然數的有限序列’的有限序列”就能表示形式證明。把上面那種將自然數的有限序列統合成一個自然數的方法連續用兩次，就能像下面這樣轉換。因此，形式證明也能用“一個自然數”來表示。
“自然數的有限序列”的有限序列→自然數的有限序列→自然數
我們用質數的乘積這種算術上的計算，根據邏輯公式得出了名為哥德爾數的自然數。那麼反過來，用質因數分解（這也是算術上的計算）應該也能根據哥德爾數得出邏輯公式。不過，我們需要驗證一下，看看使用質因數分解得到的自然數的有限序列是不是符合邏輯公式的形式。這就相當於構建一個謂詞，也就是“邏輯公式測定儀”。例如，如果我們把 792179871410815710171884926990984804119873046875000 給邏輯公式測定儀，那麼判斷結果會為真。這是因為，這個大數是 
這個邏輯公式的哥德爾數。邏輯公式是符號的有限序列。也就是說，邏輯公式可以表示為自然數的有限序列。只要恰當地定義邏輯公式，實際上就能根據算術上的計算來構建邏輯公式測定儀。
除了“邏輯公式測定儀”，我們還可以構建一些其他的有意思的謂詞，例如下面這兩個。
公理測定儀
該謂詞用於判斷給出的自然數是否為公理的哥德爾數。
證明測定儀
該謂詞用於判斷給出兩個自然數 x、y 時，
- x 是否為形式證明 A 的哥德爾數。
- y 是否為某語句 B 的哥德爾數。
以及 A 是否為 B 的形式證明。
事實上，在哥德爾不完備定理的證明中，這些“測定儀”會詳細提及。這可是“壓卷之作”呀。而且，哥德爾的證明裡甚至還出現了以下內容。
可證明性測定儀
該謂詞用於判斷給出的自然數是否能成為某個語句的哥德爾數，以及是否存在針對該語句的形式證明。
不過，判斷可證明性這回事兒跟判斷邏輯公式、公理、語句、證明相比，本身性質就不一樣，“測定儀”的說法不是很恰當。
那麼，我們現在忙的是什麼呢？
沒錯。我們正在通過構建“邏輯公式測定儀”和“證明測定儀”等，來實現用“算術”表示“形式系統”。
用“算術”表示“形式系統”。
話說回來，我們一開始就提到過構建“算術的形式系統”。這指的就是，把“算術”通過“形式系統”來從形式上表示出來。
用“形式系統”表示“算術”。
把上述兩項組合在一起，就能想到如下內容。
用“算術”表示“形式系統”，再用“形式系統”表示這裡的“算術”。
這就是“形式系統的形式系統”。
7.2.5 詞彙的整理
泰朵拉一臉疲憊地舉起雙手。
“米、米爾嘉學姐……我快不行了。”
“喔……是用詞的問題吧？”米爾嘉說道。
“嗯。出現了好多詞，我已經暈了。”
“看來需要列一個‘含義的世界’和‘形式的世界’的詞彙表。”我說道。
“這樣嗎？”米爾嘉在筆記上“沙沙”地列出了一個詞彙表。
“原來如此……”泰朵拉感歎道。看得出她鬆了口氣。
7.2.6 數項
“啊，麻煩等一下，米爾嘉學姐！”泰朵拉叫道。
“我在等啊。”米爾嘉回道。
“我不理解這個詞彙表裡的‘
或