哥德爾不完備性定理
正文
發表於1931年。它包括兩個定理：
哥德爾第一不完備性定理 設S 是包含算術系統在內的任意形式系統,則存在命題F使得F和它的否命題塡F都在S中不可證。這裡的F也稱為系統S內的不可判定句。
第二不完備性定理 在上述形式系統 S中不能證明它本身的協調性。
K.哥德爾最初想證明希爾伯特計畫中企圖證明的形式數論系統和形式實數系統的協調性。他的想法是：①證明形式數論系統的協調性；②證明形式實數系統對於形式數論系統的相對協調性。他認為①是容易證明的，因此首先考慮②的證明。在考慮②的過程中發現了第一不完備性定理，證明的方法主要是對角線方法。
希爾伯特想要在各個古典數學形式系統里，用有窮方法證明本系統的協調性。第二個完備性定理證明了即使在形式數論系統中希爾伯特計畫也無法實現，需要另謀其他出路。希爾伯特猜測只要適當選擇比系統內所含有工具更強的工具就可以證明形式數論系統的協調性。果然在1936年G.根岑實現了他的猜測。
哥德爾給出的上述S 內不可判定命題的直觀意思是“F在S內不可證”，即它的直觀是邏輯性質的。後來J.帕里斯給出了一個S內不可判定的命題,它是有明顯的數學性質的真命題。在裴里斯之後一些數學家們又做出了不少有意義的工作，其中H.弗里德曼的工作很受人注意。
第一不完備性定理的證明方法對遞歸論的早期發展有很大影響。
從無限開始
第一個面對無限的現代思想家是伽利略(Galileo)。他試圖用圓來解決。最後，他意識到，圓由一個無限多個無窮小多邊形組成。但只要他這樣做，他意識到這打開了一個可怕的不合邏輯的悖論。現在用一個無比尖銳的鉛筆，從中心畫無限多條銳利直線。他們中有無限多條，內圓應該足夠。但現在延長這些直線一直交到外圓。現在，這些線是發散的……這意味著當你到達外圓，如果你仔細的看，會有空隙。還不夠多。伽利略只是說：這講不通。如果有無限多，那應該夠了！在這一點上，他說：我們只是不明白無限！也許上帝可以，但我們有限的大腦，不能。
1866年2月6日，不滿22歲的玻爾茲曼完成了他的博士論文：“力學在熱力學第二定律中的地位和作用”。在論文中，他利用原子運動軌道閉合的假設，將熵的表示與力學的最小作用原理直接聯繫起來，試圖從純力學的角度證明熱力學第二定律。
康托爾發表了：關於無窮大的第一篇突破性論文。如果先前無窮只是一個沒完的、模糊的數，康托看到了全新的世界。康托爾做了新的一步，他說：一可以加一。好，為什麼我不能無窮加無窮？
悖論就是邏輯上的自相矛盾，似是而非，似非而是。注意，必須是邏輯上不同才是悖論。“先有雞還是先有蛋”這句話就不是悖論，因為這個問題的關鍵在於如何定義雞和蛋，和邏輯和悖論沒一點關係。
最古老的悖論是兩千多年前克里特島的“說謊者悖論”，若你說它是假命題的話.就可推出它是真命題，反之亦然。其最簡形式就是：本命題是不可證明的。這種悖論屬於語義悖論，悖論還有循環悖論等。此處從略。
哥德爾不完全性定理的由來
雖然與悖論打了幾千年交道，可數學家們不覺得他們可怕，因為他們與數學無關。直到20世紀，一小撮聰明人才隱約覺察到，在悖論中有著一些深刻的數學理論。
事情要從崇尚理性的文藝復興時期談起，當時的學者如笛卡兒、萊布尼茨等都想創造一個理論解決一切問題。萊布尼茨甚至構想把邏輯學用數學符號表示，以後每逢爭論，拿支筆一算就見分曉了。事實證明，萊布尼茨的對符號邏輯的建立起了很大作用。
萊布尼茨太超前了，沒能完成他的夙願。又過了200年，著名學者康托爾提出集合論，為統一數學提供了一線希望。
集合論的出現，標誌著數學的誕生。有了集合論，人們就沒必要（也不能）發明更廣層次的理論了。
就在數學家躊躇滿志的時候，集合論中出現了悖論。康托爾自己就發現了一個（包含一切集合的集合是否存在？），更嚴重的是羅素悖論，其中也出現了以自己為元素的集合。兩個悖論攪得數學王國不得安寧，史稱“第三次數學危機”。後來這種定義被公理排斥掉了，數學王國又恢復了平靜。不過很快，人們就意識到，這不過是“虛假的繁榮”。
不識廬山真面目，只緣身在此山中。這兩句話深刻地說明，只有站在更高的層次，才能看到更多的“風景”。那么，我們有望看到整個數學的風景嗎？
20世紀20年代，在集合論不斷發展的基礎上，大數學家希爾伯特向全世界的數學家拋出了個宏偉計畫，其大意是建立一組公理體系，使一切數學命題原則上都可由此經有限步推定真偽，這叫做公理體系的“完備性”；希爾伯特還要求公理體系保持“獨立性”（即所有公理都是互相獨立的，以保持公理系統最簡潔）和“無矛盾性”（即相容性，公理和公理之間不能是自相矛盾的）。
值得指出的是，希爾伯特所說的公理不是我們通常認為的公理，而是經過了徹底的形式化。他們存在於一門叫做元數學的分支中。元數學與一般數學理論的關係有點像計算機中應用程式和普通檔案的關係。
希爾伯特是個樂觀主義者，他的計畫也確實有一定的進展，幾乎全世界的數學家都樂觀地看著數學大廈即將竣工。正當一切都越來越明朗之際，突然一聲晴天霹靂。1931年，在希爾伯特提出計畫不到3年，年輕的哥德爾就使希爾伯特的夢想變成了令人沮喪的噩夢。哥德爾證明：任何無矛盾的公理體系，只要包含初等算術的陳述，則必定存在一個不可判定命題，用這組公理不能判定其真假。也就是說，“無矛盾”和“完備”是不能同時滿足的！這便是聞名於世的哥德爾不完全性定理。
哥德爾不完全性定理的影響
哥德爾不完全性定理一舉粉碎了數學家兩千年來的信念。他告訴我們，真與可證是兩個概念。可證的一定是真的，但真的不一定可證。某種意義上，悖論的陰影將永遠伴隨著我們。無怪乎大數學家外爾發出這樣的感嘆：“上帝是存在的，因為數學無疑是相容的；魔鬼也是存在的，因為我們不能證明這種相容性。”
但是哥德爾不完全性定理的影響遠遠超出了數學的範圍。它不僅使數學、邏輯學發生革命性的變化，引發了許多富有挑戰性的問題，而且還涉及哲學、語言學和計算機科學，甚至宇宙學。2002年8月17日，著名宇宙學家霍金在北京舉行的國際弦理論會議上發表了題為《哥德爾與M理論》的報告，認為建立一個單一的描述宇宙的大統一理論是不太可能的，這一推測也正是基於哥德爾不完全性定理。
有意思的是，在現在十分熱門的人工智慧領域，哥德爾不完全性定理是否適用也成為了人們議論的焦點。1961年，牛津大學的哲學家盧卡斯提出，根據哥德爾不完全性定理，機器不可能具有人的心智。他的觀點激起了很多人反對。他們認為，哥德爾不完全性定理與機器有無心智其實沒有關係，但哥德爾不完全性定理對人的限制，同樣也適用於機器倒是事實。
哥德爾不完全性定理的影響如此之廣泛，難怪哥德爾會被看作當代最有影響力的智慧巨人之一，受到人們的永恆懷念。美國《時代》雜誌曾評選出20世紀100個最偉大的人物，在數學家中，排在第一的就是哥德爾。
對哥德爾定理的一些誤解
由於哥德爾的第一條定理有不少誤解。我們舉出一些例子：
該定理並不意味著任何有意義的公理系統都是不完備的。該定理需假設公理系統可以“定義”自然數。不過並非所有系統都能定義自然數，就算這些系統擁有包括自然數作為子集的模型。例如，歐幾里得幾何可以被一階公理化為一個完備的系統（事實上，歐幾里得的原創公理集已經非常接近於完備的系統。所缺少的公理是非常直觀的，以至於直到出現了形式化證明之後才注意到需要它們），塔斯基（Tarski）證明了實數和複數理論都是完備的一階公理化系統。這理論用在人工智慧上，則指出有些道理可能是我們能夠判別，但機器單純用一階公理化系統斷卻無法得知的道理。不過機器可以用非一階公理化系統，例如實驗、經驗。
討論和推論
不完備性的結論影響了數學哲學以及形式化主義（使用形式符號描述原理）中的一些觀點。我們可以將第一定理解釋為“我們永遠不能發現一個萬能的公理系統能夠證明一切數學真理，而不能證明任何謬誤”
以下對第二定理的另一種說法甚至更令人不安：
如果一個（強度足以證明基本算術公理的）公理系統可以用來證明它自身的相容性，那么它是不相容的。於是，為了確立系統S的相容性，就要構建另一個系統T，但是T中的證明並不是完全可信的，除非不使用S就能確立T的相容性。舉個例子，自然數上的皮亞諾公理的相容性可以在集合論中證明，但不能單獨在自然數理論範圍內證明。這對大衛·希爾伯特的著名的未解決的23個數學問題中的第二個給出了一個否定回答。
理論上，哥德爾理論仍留下了一線希望：也許可以給出一個算法判定一個給定的命題是否是不確定的，讓數學家可以忽略掉這些不確定的命題。然而，對可判定性問題的否定回答表明不存在這樣的算法。
要注意哥德爾理論只適用於較強的公理系統。“較強”意味著該理論包含了足夠的算術以便承載對第一不完備定理證明過程的編碼。基本上，這就要求系統能將一些基本操作例如加法和乘法形式化，例如在魯賓遜算術Q中那樣。有一些更弱的公理系統是相容而且完備的，例如Presburger算術，它包括所有的一階邏輯的真命題和關於加法的真命題。
公理系統可能含有無窮條公理（例如皮亞諾算術就是這樣），但要哥德爾定理生效，必須存在檢驗證明是否正確的有效算法。例如，可以將關於自然數的所有在標準模型中為真的一階語句組成一個集合。這個公理系統是完備的；哥德爾定理之所以無效是因為不存在決定任何一條語句是否公理的有效算法。從另一方面說，這個算法的不存在正是哥德爾定理的直接結果。
另一個哥德爾定理不適用的特殊情況是：將關於自然數的所有語句首先按長度然後按字典順序排序，並從皮亞諾公理集開始，一個一個遍歷列表，如果發現一條語句既不能證明又不能否證，就將它作為公理加入。這樣得到的系統是完備的，兼容的，並且是足夠強大的，但不是遞歸可枚舉的。
哥德爾本人只證明了以上定理的一個較弱版本；以上定理的第一個證明是羅梭(Russel)於1936年給出的。
基本上，第一定理的證明是通過在形式公理系統中構造如下命題
p=“此命題是不可證明的”來完成的。這樣，它可以看成是說謊者悖論的一個現代變種。
如果公理系統是相容的，哥德爾證明了p（及其否定）不能在系統內證明。因此p是真命題（p聲稱它不可證明，而它確實不能），儘管其證明不能在系統內形式化。請注意將p作為公理加入系統並不能解決問題：擴大了的系統中會有另一個哥德爾語句出現。
羅傑·彭羅斯聲稱“可被機械地證明的”和“對人類來說看起來是真的”的這一區別表明人類智慧型不同於自然的無意識過程。這一觀點未被普遍接受，因為正如MarvinMinsky所指出的，人類智慧型有犯錯誤和理解不相容和謬誤句子的能力。但MarvinMinsky透露說庫爾特·哥德爾私下告訴他，他相信人類有一種到達真理的直覺方法，但因為跟計算機式的方法不同，人類可以知道為真的事情並不受他的定理限制。
對以上認為該定理揭示了人類具有超出形式邏輯之能力的這種觀點也可以作如下評論：我們其實不知道p是真是假，因為我們並不（也無法）知道系統是否是相容的。因此實際上我們並不知道系統之外的任何真理。我們所確知的只有這樣一個命題：
要么p在系統內部無法證明，要么該系統是不相容的。這樣的命題之前已經在系統內部被證明。實際上，這樣的證明已經給出。
解集的概念。
(一)集合
“集合”或集的描述：集這個概念，是不可以精確定義的數學基本概念之一，故只能作描述：凡具有某種特殊性質對象的匯集，其總合被稱為集。
例：一組數(可能是無限的)，一群人，一欄雞蛋。
在作數學上具體研究時，組成集的個體，被稱為“元”的其他特殊屬性，如雞的特性，人的特性，數的特性，都不再考慮。於是，一個集合就被抽象成A，它的元被抽象成x。
我們有x屬於A
我們也規定：A不能屬於A
即A不能是A自己的一元，這個規定不是不合理的，例如，所有的書所組成的集不是書！
所以所有書的集合不能是這個集合的一元。
A的某一部份B也可自行構造出一集，被稱為A之“子集”。
我們有B含於A
特殊情況：B可以等於A，B也可以沒有元素，被稱為“空集”，我們稱這樣兩種情況叫住 A的“平凡”子集。
定義：對等
設A，B分別為兩個集，如果A和B之間能建立1-1的對應關係，則我們稱：A對等於B
反之亦然。
對等是集與集之間最基本的關係。若A和B都含有限個元，則兩集之間要對等，若且唯若二者的元的數目相等。
如果A和B都是無限的，則也能/不能建立對等關係，如兩個無限數列A和B：
A：1，2，3，。。。
B：2，4，6，。。。
就能建立1-1對應，故A對等於B
可以證明，任何兩個無限數列的集合都能對等。
但是，有些無限集之間卻不能對等。
例：設實數軸0到1之間的所有有理數所組成的集為R，又設0到1之間所有的無理數所組成的集為I，則可證明(略)：
1.R和I之間不對等；
2.R對等於I中的一個非平凡子集，在這樣的情況下，綜合1。，我們說 R小於I
3.R對等於一個自然數序列數目在無限大時候的推廣。我們稱上述A有“勢”為可數勢，意味著，A的元數目可以一個一個地數下去，雖然不一定能數完。於是，自然數序列集具有可數勢，任何有限集合也有可數勢，而且，由上面的3.可知有理數集也有可數勢。
再從1.的結論可知，無理數的集有大於可數勢的勢，我們稱這個勢為“不可數勢”！
(二)“康脫悖論”
設M是一個集，這個集的元是由集合X所組成，其中，X不屬於X。
康脫悖論：M不屬於M同時M屬於M
事實上，如果M屬於M，則由定義，M不屬於M；反過來，如果M不屬於M，則同樣由定義，M屬於M。
這就出現了悖論，這個悖論首先由康脫提出來， 它類似於“塞維爾村理髮師悖論”，1902年，羅素又把它在敘述上修改了一下，把它作為一種悖論，用來說明集合論的形式公理體系建立的必要。
康脫悖論的發現，引起了十九世紀末的數學界很大的震動，原因在一切數學的推理和由推理得出的結論最終可以由“與、或、非”三種基本邏輯運算所構成的組合操作，而這些組合操作的集合本身構成了矛盾，於是所有數學成就的整個大廈開始動搖！
其後，羅素等人提出了形式(邏輯)公理體系，試圖甩掉那些悖論，讓數學在無悖論的情況下發展(事實上，至今數學裡還沒有這樣的悖論的干擾)。辦法就是，如懷特海所說，當一個形式邏輯體系出現康脫悖論時，就用一個更大的邏輯體系去把它包了，換句話說，就是讓原先那個邏輯體系作為更大的邏輯體系的子集合。當然這樣做的結果，新的母體系又產生了不可避免的矛盾。懷特海問：就這樣一層一層地包下去，以致於無窮，是否就可避免了矛盾？
(三)哥德爾不完備性定理淺釋
哥德爾不完備性定理的提出和證明就是為了解決懷特海上述猜想，它指出：使用層層外延法擴張形式邏輯體系並不能清除其總和的矛盾！
哥德爾最妙的想法就是把一切邏輯運算視作一種二進制代碼(CODE)，就例如，“與”可對應為1，“或”可對應為10，“非”可對應為11。但這些二進制數卻被他再轉換成小數，如0.1，0.01，0.11，組合邏輯運算不過是這三種碼的組合，也就是更複雜的小數。
遞歸：邏輯運算里有一種調用自身的運算，稱為“遞歸”。遞歸術語今天是編程算法里最基本的運算方法之一。遞歸有兩種結局：1.終止於有限次數的操作；2.無限遞歸下去，在編程上被稱為死循環。
當邏輯體系按照懷特海的辦法延拓到一個新的，更大的邏輯體系時，舊的邏輯體系中的操作如果被新的體系調用，就會出現遞歸，遞歸有時是無限次數的(這是允許的，不象計算機運算不允許)，在此情況下，由二進制代碼所代表的邏輯運算將出現無限循環的小數。
這樣，哥德爾就用遞歸把每一次形式邏輯體系的外延後的操作，用有限小數和無限循環小數代表出來，而且他還證明了，這種代表是唯一對應的，也就是說，每一二進制有限小數或無限循環小數皆唯一對應於懷特海意義下的無限擴張邏輯體系下的某一邏輯操作。
二進制與十進制：二進制數與十進制數之間能建立起唯一對應關係，因之，實軸上0-1的一端(剃除掉兩個端點，0、1)的所有小數都可以由二進制小數表出，而且，兩種進位制里的有限小數和無限循環小數都對應。
有理數和無理數：任何有限小數和無限不循環小數都屬於0-1之間的有理數。0-1數段的實數除了全部含於其中的有理數以外，還存在著無理數，例如2分之2的平方根。如果我們表0-1數段的所有有理數集合為Ro，表剩下的所有無理數集合為Io，則可證明：
Ro對等於R;
Io對等於I
這裡的R、I見(一)中例的定義。因此，我們遂有Ro有可數勢，而Io有不可數勢。
哥德爾證明了：懷特海意義下的無限延拓形式邏輯體系的所有邏輯操作所組成的集合與Ro之間能夠建立起1-1的對應關係，也就是說，這兩個集合對等，因此，它們有相同的勢。即都具有可數 勢。
但是，如果我們把0-1間任意一個無理數對應成一個邏輯操作，因為它無限不循環，這個操作是我們不能確定的，但卻能有限截斷後知道的，我們就可以理解成不能用確定的邏輯操作去解決的，或者換個口吻，說成是矛盾。
於是，哥德爾就得出了結論，形式邏輯分析不能用來解決認識中的所有出現的矛盾，更有甚者，我們由Io的不可數勢的性質看到，這樣的矛盾遠多於形式邏輯分析所能解決的數量！
哥德爾定理證明的獨到之處，在於用數學反過來證明邏輯分析問題，前面我們已經看到，數學上已經確定了的推理本來是可被拆成基本邏輯操作來推理的。羅素曾有個想法，認為所有數學的推理都可拆開成基本的邏輯運算去實現，好象是數學可以變成邏輯學似的，今天的哲學界數學界擯棄了羅素這個想法，認為這是不可能的。。
