0☆難度：說謊者悖論
這句話是假的。
換個表示，G=這句話是假的。
如果G為真，G表述G為假，矛盾；如果G為假，G表述的就是「G為假」，所以G為真，矛盾。
1☆難度：理髮師悖論
小鎮只有一個理髮師，他聲稱：「只給（不給自己理髮的人）理髮」，那麼他該不該給自己理髮？
如果理髮，那麼他不是（不給自己理髮的人），他不能理髮；如果不理，那麼他是（不給自己理髮的人），他可以給自己理髮。
兩個悖論，其實都是自我指涉的問題，它陳述了自己，而且對自我進行了否定。哥德爾證明實際就是上述悖論的變種。他構造了一個陳述G，G=「此陳述不可證明」。
如果G為真，G就不可證明。（系統不完備）如果G為假，即，此陳述可證，那麼G為真。（系統得出G假且G真，系統有矛盾）即，無矛盾的（包含算術的）系統內，總有陳述是真的，可是沒法證明。
哥德爾的證明還在繼續，那麼G為真，我們將G作為公理，加入原來的（不完備的）公理系統，在這個增補的公理系統中，還可以繼續構建類似G的陳述，即增加公理並不能解決問題。
證明還有繼續，可是目前說不清楚，留待下篇。為了理解哥德爾的構造方法，我們先再來看一個悖論。
2☆難度：理察悖論
所有的陳述，無論是用英文表達，還是用中文表達，可以用字數和字母（拼音）順序做一個排序。
例如，「一個整數可以被另一個整除」，12個漢字，設它的序號是20.（隨便什麼數字，只是舉例。）
字數少的排在字數多的前面，字數相同的按照字母（拼音）順序，總之，每一個陳述都對應一個唯一的整數，代表它在所有陳述之中的位置。
有時，這個序號數字，具有它代表的陳述的性質。假設：17號陳述是「不能被1和其自身以外的其他整數整除」。而17確實不能被1和其自身以外的其他整數整除。我們說，17不是理察數。有時，這個序號數字，不具有它代表的陳述的性質。假設：15號陳述是「某一個整數與這一整數自身的乘積」。15不是某一個整數與這一整數自身的乘積。我們說，15是理察數。陳述「是理察數」在文字序列中，必然有個序號，隨便假設其序號為5，即，5號陳述是「是理察數」。那麼，5是不是理察數？
如果，5是理察數，按照理察數的定義，5不具有5號陳述的性質，即5不是理察數，矛盾；如果5不是理察數，按照定義，5具有5號陳述的性質，即5是理察數，矛盾。據說，理察悖論出現矛盾的地方在於，沒有區分開數學和元數學，反正我區分不開，而哥德爾的證明避開了這樣的錯誤，但構造的過程是類似的。
哥德爾虛構了一個系統PM。
這裡有12個原始符號，採用1~12來作為它們的哥德爾數；三個數字變量x、y、z，分別使用13、17、19作為哥德爾數。如圖，有個直觀印象就好，後面所有涉及符號的地方，我都會翻譯的。
其中，s是數的直接後繼，例如：s0表示1，ss0表示2，sss0表示3，依次類推。
形式系統中的符號，本應是毫無意義的，僅僅是「空洞的符號」，系統中，定理的推導僅靠形式規則。為了可讀性，選擇的符號，和它的通常意義相同。
數字變量y的哥德爾數是17，這個我們將多次用到。
哥德爾首先證明了：
每一個算數真理，用系統PM表達的話，都是一個定理；每一個系統PM的定理，按照符號的通常意義解釋，都代表了相應的算數真理。
前方高能（下篇），即將開始3☆難度的哥德爾證明。