如果人的心靈會被化簡為幾條僵化的規則，那將是一件令人悲哀的事。幸運的是，哥德爾證明了，情況不會如此。——霍夫斯塔特
理髮師悖論講的是，理髮師只為不給自己理髮的人理髮，那麼他自己應該給自己理髮嗎？
希爾伯特說，只要把理髮師和其他人強行區分，這樣問題就不成立了。正如現實生活中，任何事情總有特例存在。但是哥德爾說了，你區分了一個理髮師，就會產生另一個理髮師悖論，沒完沒了。這就是著名的哥德爾不完備性定理——任何數學系統必然存在既不能證明也不能證偽的命題。這意味著，沒有一個數學系統比其它的更優越，正如相對論那樣，沒有一個參考系比其它的更特殊。
哥德爾&愛因斯坦
之前已經介紹過哥德爾和愛因斯坦的關係，還有一致性問題的由來，下面直接給出該定理的證明。
定義哥德爾數
哥德爾首先建立了一套完整的數學系統（形式演算系統），簡而言之就是對算術關係的符號描述，它遵循了希爾伯特的純粹性理念，把一切有意義的內容都轉化為一堆無意義的符號。需要注意的是，機械性的符號運算等價於數學概念，例如象棋，不必把棋子“車”理解為戰車，“馬”理解為戰馬，只需要定義每個棋子的移動規則，車走直線，馬走日字就可以了。
下一步構建符號和數學含義的一一對應，並賦予每個符號一個固定的數字，即哥德爾數。這樣做的目的，就是讓系統內的任何數學公式，都可以用機械性符號代替。
固定符號的哥德爾數
例如數學概念“0不等於1”表述成符號串為“~(0=s0)” ，其中s0表示0的直接後繼，也就是1，同理ss0表示2。除了十二個固定符號和含義的對應外，其餘數字變量x、y、z等，都賦予一個大於12的不同素數。
變量的
公式的哥德爾數
總而言之，哥德爾建立了基礎的符號與哥德爾數的一一對應。舉個例子，“存在x，x是y的直接後繼”，表達成字符串就是(∃x)(x=s y)。
這個符號序列中每個基本符號都對應一個哥德爾數，將每個哥德爾數作為指數，賦給素數數列(2、3、5、7、11...)，換言之，每一個素數各加一個對應於相應符號的哥德爾數作為指數，然後彼此相乘得出唯一的一個數字m，這就是公式的哥德爾數。
哥德爾數的性質
根據完整的對應關係，可以判斷出任何一個數字，是不是一個公式的哥德爾數，只要對它進行因式分解，就可以還原成公式的字符串。例如給出數字“243000000”，就可以逆向推出它的公式“(0=0)”，繼而得出數學含義“零等於零”。
無差別算數化
在數學系統中每一個表達式都對應了一個特定的哥德爾數，通過因式分解，可以分析出哥德爾數的性質。因此，無論公理或定理，都可以被理解成對應哥德爾數的算術關係的問題。簡而言之，公理或定理都可以“算術化”。
哥德爾這一步是想說明，狹義上元數學和數學之間沒有本質的區別，廣義上任何數學系統之間都存在相同的聯繫。
舉個例子，給出一個公式“~(0=s0)”，它的含義是零不等於一，可以得到公式的哥德爾數m是2^1×3^8×5^6×7^5×11^7×13^6×17^9，當然這是一個相當大的數。
下一步通過分析哥德爾數m的算數性質，可以得到一個定理，它可以準確描述公理“~(0 =s0)”本身。如此一來，元數學命題可以映射為一個數學命題，就證明了元數學和數學之間沒有本質區別。
關鍵步驟在於，仔細觀察哥德爾數m中的第一個因數2，它表明了m可以被2整除，但是不能被4整除這一算數性質，而這個性質可以表述為一個定理“存在一個數z，m等於z乘以2，並且不存在數z，m等於z乘以2×2”，字符串表示為：
也就是說，符號“~”，可以由以上定理準確描述，同理，哥德爾數m中的任何一個因數都可以如此描述，最後整個字符串非常長，但原理十分簡單，重要的是它完整翻譯了“~(0=s0)”這個元數學命題。
這就是“無差別算術化”的意義：一組符號串在排列上的性質，可以通過因式分解哥德爾數得到素因子之間的關係，以一種間接但又十分精確的方式來描述 。
其實到這裡，哥德爾就已經說明了，悖論是不能通過區分來解決的。接下來就是最後一步，只要在哥德爾建立的數學系統中，構造一個符號串悖論，相當於理髮師悖論，這樣就完成了證明。
哥德爾最後的證明
為了讓整個證明看起來比較簡潔，哥德爾定義了幾個函數 ，以替代相當長的公式串。
公式Dem(x,z)，表示整數x和z之間的算術關係，其數學含義是：哥德爾數為x的公式序列是哥德爾數為z的公式的證明，簡言之，公式z可證。
公式Sub(x,17,x)，關於哥德爾數x的函數，其數學含義是：取一個哥德爾數是x的公式，其中凡是有變量y(哥德爾數17對應的變量是y)出現的地方均用哥德爾數x的數字替換，得到的新公式就是Sub(x,17,x)，該公式的哥德爾數用小寫sub(x,17,x)表示。
舉個例子，假設公式(∃x)(x=sy)的哥德爾數為m，則Sub(m,17,m)就表示為：
(∃x)(x=s s...ss0)，其中 s...ss0就是數字m的字符串，0之前有m個s。
下一步，哥德爾需要模仿理髮師悖論，構造一個“自指”的字符串悖論，即在該數學系統下，構造一個公式G，其含義是公式G不可證。
1、給出公式
~(∃x)Dem(x, z)
其含義是：不存在x，哥德爾數為x的公式序列是哥德爾數為z的公式的證明，即哥德爾數為z的公式是不可證的。
2、找出上述公式的一個特例：
~(∃x)Dem(x,Sub(y,17,y))
其含義是：哥德爾數為sub(y,17,y)的公式是不可證的。需要注意的是，這個公式中含有變量y。
3、為了確定公式的含義，我們還需要用數字替換變量y，假設公式~(∃x)Dem(x,Sub(y,17,y))的哥德爾數為n，將n替換y得到公式G：
~(∃x)Dem(x,Sub(n,17,n))
其含義是哥德爾數為sub(n,17,n)的公式是不可證的，因為其中沒有變量，所以G的意義是確定的。
4、公式G也是一個字符串，因此也有一個哥德爾數g，而g等於sub(n, 17, n)。因為用公式~(∃x)Dem(x,Sub(y,17,y))的哥德爾數n替換y，剛好就是Sub(n,17,n)函數的操作，所以Sub(n,17,n)對應的哥德爾數sub(n,17,n)，就是公式G的哥德爾數。
5、至此，公式G的含義為：哥德爾數為g的公式是不可證的，即公式G不可證。也可以表達為：G可證，當且僅當~G可證，或者~G可證，當且僅當G可證。簡言之，G不是一個可以判定的命題。因此，該數學系統中必然存在既不能證明也不能證偽的命題——哥德爾不完備性定理。
很多人不能夠理解最後一步，原因可能是沒有理解Sub(n,17,n)函數的定義及規則，也可能是對自指的概念接觸較少。總而言之，多讀多看，其義自見。
哥德爾的證明被愛因斯坦稱讚為“近年來對科學所做的最偉大貢獻之一”，並授予了“阿爾伯特·愛因斯坦獎”。它不僅僅是一個數學理論，而是揭示了自然的本質，當你讀懂的那一刻，會顛覆你的世界觀。
