哥德爾不完備定理

哥德爾不完備定理 (Gödel's incompleteness theorems) 是一條有關數理邏輯的重要定理,說實話,我絕對談不上認識這條定理,不過有些感想想與大家談談。

古希臘歐幾里得幾何,由一小撮基本定義 (definition) 和公理 (axiom),證明出新的定理 (theorem)。而藉由定義、公理和定理,亦可證明千千萬萬更多新的定理。

一套很完善的系統吧?除了歐氏幾何外,其他數學能否以這種邏輯體系表現出來?十九、二十世紀的數學家,如康德 (Georg Cantor)、羅素 (Bertrand Russell) 等在數學基礎上作出了很大的努力,例如集合論的創立等。後來希伯特 (David Hilbert) 提出了希伯特計劃 (Hilbert's project)。希爾伯特計劃,是想以形式系統 (formal system) 來表現數學,即是希望以有限的公理作為數學根基,並希望能證明出這種系統是相容 (consistent) 和完備 (complete) 的。

相容和完備是兩個很重要的概念,亦是我們追求的理想境界。何謂相容?何謂完備呢?

相容的意思,是指在系統內合法的推理下不會推導出矛盾的結果。例如「我是男人」及「我不是男人」這兩個命題不可能均被證明為真的。

而完備的意思,是指系統內的命題均可被證明。

因此,在一個「相容」兼「完備」的系統內,「我是男人」及「我不是男人」中,只少有一個命題可被證明為真。

大家試想一想,如果系統不相容,推導出來的結果並不可靠。如果不完備,便要接受有些結果是無法被證明出來。同時具備相容及完備,那真是最好不過呢!

但在1930年代,哥德爾 (Kurt Gödel) 的兩條不完備定理,否定了希伯特計劃。

簡單來說,第一不完備定理指出滿足某條件的相容形式系統中,會有在該系統中不能被證明的命題,即是不完備,而第二不完備定理指出滿足某條件的相容系統不能由該系統證明自身的相容性。

當中的「某條件」,我不在此多加解釋。但注意,不完備定理是應容於滿足「某條件」的系統。確會存在既相容又完備的系統,例如兩千多年前歐幾里得的歐氏幾何,補上一些基本的公理後是一個完備又相容的系統。但並不是所有系統均可這樣做。

數學,講到這樣。大家已經悶死吧?

追求相容的同時,原來要犧牲當中的完備性。完美是不存在吧?至少在某條件之下……

活在當下,我們不得不承認有些東西是做不來、做不到。盲目追求完美,其實是一件虛無飄渺的事情,但這不代表我們做事求求其其便可,人生過得求求其其亦可。在一些框架下,總有很多東西可以做,在此框架下把事情做好。但事情都未做好,甚至未開始去做,便去想如何做到「最」好,做到「完美」,是否不切實際呢?


這篇粗疏的文章,可能當中會有錯漏,請見諒。如果大家對哥德爾不完備定理有興趣,我有些書籍可以推介一下:
1. 《數學女孩 — 哥德爾不完備定理》,作者為結成浩。
結成浩這個數學女孩系列,日本已出版了五冊,台灣世茂翻譯了四冊。這是一部數學小說,每冊都以通俗易懂的手法由淺入深帶出最後該冊的主題。不過在哥德爾不完備定理,最後一章是要帶出該該定理的證明,我功力有限看不懂呢 :P
另外,世茂這個系列,翻譯常有出錯。不過我又不懂日文,不知原版如何。
2. Godel's Proof, by Ernest Nagel
http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371
這本小書不是小說形式,但也算易懂,香港誠品也見有售。我懷疑數學女孩中的一些鋪排也是參考此書。


本文同步於 http://deadfatboy.blogspot.hk/2013/09/blog-post.html 發表