數學女孩3 哥德爾不完備定理

結城浩

生於1963年。日本知名技術作家和程序員。在編程語言、設計模式、數學、加密技術等領域，編寫了很多深受歡迎的入門書。代表作有《數學女孩》系列、《程序員的數學》、《圖解密碼技術》等。

作者主頁：http://www.hyuki.com

序言

第 1章　鏡子的獨白　1

1.1　誰是老實人.1

1.1.1　鏡子呀鏡子.1

1.1.2　誰是老實人.3

1.1.3　相同的回答.7

1.1.4　回答是沈默.8

1.2　邏輯謎題.9

1.2.1　愛麗絲、博麗絲和克麗絲.9

1.2.2　用表格來想　10

1.2.3　出題者的心思　14

1.3　帽子是什麼顏色　15

1.3.1　不知道　15

1.3.2　對出題者的驗證　18

1.3.3　鏡子的獨白　19

第 2章　皮亞諾算術　23

2.1　泰朵拉　23

2.1.1　皮亞諾公理　23

2.1.2　無數個願望　27

2.1.3　皮亞諾公理.PA1.28

2.1.4　皮亞諾公理.PA2.29

2.1.5　養大　32

2.1.6　皮亞諾公理 PA3.34

2.1.7　小的？　35

2.1.8　皮亞諾公理.PA4.36

2.2　米爾嘉　39

2.2.1　皮亞諾公理 PA5.42

2.2.2　數學歸納法　43

2.3　在無數腳步之中　49

2.3.1　有限？無限？　49

2.3.2　動態？靜態？　50

2.4　尤裏　52

2.4.1　加法運算？　52

2.4.2　公理呢？　53

第3章　伽利略的猶豫　57

3.1　集合　57

3.1.1　美人的集合　57

3.1.2　外延表示法　58

3.1.3　餐桌　60

3.1.4　空集　61

3.1.5　集合的集合　62

3.1.6　公共部分　64

3.1.7　並集　67

3.1.8　包含關系　68

3.1.9　為什麼要研究集合　71

3.2　邏輯　72

3.2.1　內涵表示法　72

3.2.2　羅素悖論　74

3.2.3　集合運算和邏輯運算　77

3.3　無限　79

3.3.1　雙射鳥籠　79

3.3.2　伽利略的猶豫　83

3.4　表示　86

3.4.1　歸途　86

3.4.2　書店　87

3.5　沈默　88

第4章　無限接近的目的地　91

4.1　家中　91

4.1.1　尤裏　91

4.1.2　男生的“證明”　92

4.1.3　尤裏的“證明”　93

4.1.4　尤裏的“疑惑”　96

4.1.5　我的講解　97

4.2　超市　99

4.3　音樂教室　104

4.3.1　字母的導入　104

4.3.2　極限　106

4.3.3　憑聲音決定音樂　108

4.3.4　極限的計算　111

4.4　歸途　119

第5章　萊布尼茨之夢　123

5.1　若尤裏，則非泰朵拉　123

5.1.1　“若……則……”的含義　123

5.1.2　萊布尼茨之夢　126

5.1.3　理性的界限？　128

5.2　若泰朵拉，則非尤裏　129

5.2.1　備戰高考　129

5.2.2　上課　131

5.3　若米爾嘉，則米爾嘉　133

5.3.1　教室　133

5.3.2　形式系統　135

5.3.3　邏輯公式　137

5.3.4　“若……則……”的形式　140

5.3.5　公理　142

5.3.6　證明論　143

5.3.7　推理規則　145

5.3.8　證明和定理　147

5.4　不是我，還是我　149

5.4.1　家中　149

5.4.2　形式的形式　150

5.4.3　含義的含義　152

5.4.4　若“若……則……”，則……　153

5.4.5　邀約　157

第6章　-δ語言　159

6.1　數列的極限　159

6.1.1　從圖書室出發　159

6.1.2　到達階梯教室　160

6.1.3　理解復雜式子的方法　164

6.1.4　看絕**　166

6.1.5　看“若……則……”　169

6.1.6　看“所有”和“某個”　170

6.2　函數的極限　174

6.2.1　-δ　174

6.2.2　-δ的含義　177

6.3　摸底考試　178

6.3.1　上榜　178

6.3.2　靜寂的聲音、沈默的聲音　179

6.4　“連續”的定義　181

6.4.1　圖書室　181

6.4.2　在所有點處都不連續　184

6.4.3　是否存在在一點處連續的函數　186

6.4.4　逃出無限的迷宮　187

6.4.5　在一點處連續的函數！　188

6.4.6　訴衷腸　192

第7章　對角論證法　197

7.1　數列的數列　197

7.1.1　可數集　197

7.1.2　對角論證法　201

7.1.3　挑戰：給實數編號　209

7.1.4　挑戰：有理數和對角論證法　213

7.2　形式系統的形式系統　215

7.2.1　相容性和完備性　215

7.2.2　哥德爾不完備定理　222

7.2.3　算術　224

7.2.4　形式系統的形式系統　225

7.2.5　詞匯的整理　229

7.2.6　數項　229

7.2.7　對角化　230

7.2.8　數學的定理　232

7.3　失物的失物　233

第8章　兩份孤獨所衍生的產物　239

8.1　重疊的對　239

8.1.1　泰朵拉的發現　239

8.1.2　我的發現　245

8.1.3　誰都沒發現的事實　246

8.2　家中　247

8.2.1　自己的數學　247

8.2.2　表現的壓縮　247

8.2.3　加法運算的定義　251

8.2.4　教師的存在　254

8.3　等價關系　255

8.3.1　畢業典禮　255

8.3.2　對衍生的產物　257

8.3.3　從自然數到整數　258

8.3.4　圖　259

8.3.5　等價關系　264

8.3.6　商集　268

8.4　餐廳　272

8.4.1　兩個人的晚飯　272

8.4.2　一對翅膀　272

8.4.3　無力考試　275

第9章　令人迷惑的螺旋樓梯　277

9.1　π弧度　277

9.1.1　不高興的尤裏　277

9.1.2　三角函數　279

9.1.3　sin45°　282

9.1.4　sin60°　286

9.1.5　正弦曲線　290

9.2　π弧度　294

9.2.1　弧度　294

9.2.2　教人　296

9.3　π弧度　297

9.3.1　停課　297

9.3.2　余數　298

9.3.3　燈塔　300

9.3.4　海邊　303

9.3.5　消毒　304

第 10章　哥德爾不完備定理　307

10.1　雙倉圖書館　307

10.1.1　入口　307

10.1.2　氯　308

10.2　希爾伯特計劃　310

10.2.1　希爾伯特　310

10.2.2　猜謎　312

10.3　哥德爾不完備定理　316

10.3.1　哥德爾　316

10.3.2　討論　318

10.3.3　證明的概要　320

10.4　春天—形式系統 P.320

10.4.1　基本符號　320

10.4.2　數項和符號　322

10.4.3　邏輯公式　323

10.4.4　公理　324

10.4.5　推理規則　327

10.5　午飯時間　328

10.5.1　元數學　328

10.5.2　用數學研究數學　329

10.5.3　蘇醒　329

10.6　夏天—哥德爾數　331

10.6.1　基本符號的哥德爾數　331

10.6.2　序列的哥德爾數　332

10.7　秋天—原始遞歸性　335

10.7.1　原始遞歸函數　335

10.7.2　原始遞歸函數（謂詞）的性質　338

10.7.3　表現定理　340

10.8　冬天—通往可證明性的漫長之旅　343

10.8.1　整理行裝　343

10.8.2　數論　344

10.8.3　序列　346

10.8.4　變量·符號·邏輯公式　348

10.8.5　公理、定理、形式證明　358

10.9　新春—不可判定語句　362

10.9.1　“季節”的確認　362

10.9.2　種子—從含義的世界到形式的世界　364

10.9.3　綠芽—p的定義　366

10.9.4　枝杈—r的定義　367

10.9.5　葉子—從 A1往下走　368

10.9.6　蓓蕾—從 B1開始往下走　369

10.9.7　不可判定語句的定義　369

10.9.8　梅花—.IsProvable(g).370

10.9.9　桃花—.IsProvable(not(g))的證明　372

10.9.10　櫻花—證明形式系統 P是不完備的　374

10.10　不完備定理的意義　376

10.10.1　“‘我’是無法證明的”　376

10.10.2　第 二不完備定理的證明之概要　380

10.10.3　不完備定理衍生的產物　383

10.10.4　數學的界限？　384

10.11　帶上夢想　386

10.11.1　並非結束　386

10.11.2　屬於我　387

尾　聲　391

後　記　395

參考文獻和導讀　399