希爾伯特希望世上所有一切的數學問題都可以從公理出發去得到解答。但後來由哥德爾提出了哥德爾不完備定理指出，希爾伯特計劃大多數目標都無法實現。

數學邏輯問題

例如理髮師悖論這個問題，小城裡的理髮師放出豪言：他要為城裡人刮鬍子，而且一定只要為城裡所有「不為自己刮鬍子的人」刮鬍子。
但問題是：理髮師該為自己刮鬍子嗎？如果他為自己刮鬍子，那麼按照他的豪言「只為城裡所有不為自己刮鬍子的人刮鬍子」他不應該為自己刮鬍子；但如果他不為自己刮鬍子，同樣按照他的豪言「一定要為城裡所有不為自己刮鬍子的人刮鬍子」他又應該為自己刮鬍子。
理髮師悖論模糊了是非，這顯示出了數學還不夠嚴謹，因此希爾伯特(Hilbert)提出了一個概念，就是在每個數學領域提出了一些公理，利用這些公理去推導出所有的數學問題。

希爾伯特計劃(Hilbert’s Program)

希爾伯特計劃是由德國數學家大衛‧希爾伯特在1920年代提出的一個數學計畫。它是一個關於公理系統相容性的嚴謹證明的一項計劃。他認為只要數學符合以下的目標，就一切數學問題都能解決了

完備性

所有的真命題都可以由公理出發而得到證明。

一致性

整個體系不存在矛盾。

可判斷性

存在一個算法可以判定任意一個命題是否可以從公理出發證明。

必要概念

在數論(Number theory)中，哥德爾編號是對某些形式語言的每個符號和公式指派一個叫做哥德爾數(GN)的唯一的自然數的函數。這個概念是哥德爾為證明他的哥德爾不完備定理而引入的。

數學符號的哥德爾數

變量符號的哥德爾數

例如\(0\times x=0\)這個命題的哥德爾數為 \[\begin{aligned} 2^6 \times 3^{12} \times 5^{13} \times 7^5 \times 11^6 = 123620768045516171875000000 \end{aligned}\]

皮亞諾公理(Peano axioms)

證明1是存在的

依據皮亞諾公理(Peano axioms)每個自然數都存在後繼數，因此0的後繼數1存在。

邏輯表示：

\[\begin{aligned} (\exists x)(x=sy)\\ (\exists x)(x=s0) \end{aligned}\]

哥德爾數表示：

\[\begin{aligned} 2^8 \times 3^{4} \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^{5} \times 19^{7} \times 23^{17} \times 29^{9} \\ 2^8 \times 3^{4} \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^{5} \times 19^{7} \times 23^{6} \times 29^{9} \end{aligned}\]

整體證明過程的哥德爾數表示：

\[\begin{aligned} 2^{2^8 \times 3^{4} \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^{5} \times 19^{7} \times 23^{17} \times 29^{9}} \times 3^{2^8 \times 3^{4} \times 5^{13} \times 7^9 \times 11^8 \times 13^{13} \times 17^{5} \times 19^{7} \times 23^{6} \times 29^{9}} \end{aligned}\]

命題的命題

如果我現在想表示「\(0+1=2\)這個命題第2個符號為\(+\)」要如何表示？
對於「\(0+1=2\)」這個命題的邏輯和哥德爾數寫法是

邏輯表示：

\[\begin{aligned} 0+s0=ss0 \end{aligned}\]

哥德爾數表示：

\[\begin{aligned} 2^6 \times 3^{11} \times 5^{7} \times 7^6 \times 11^5 \times 13^{7} \times 17^{7} \times 19^{6} \end{aligned}\] 顯然可以知道對於「\(0+1=2\)」這個命題中的\(+\)號代表的部分為\(3^{11}\)，如果不是\(+\)號則代表的部分不會是\(3^{11}\)，因此對於「\(0+1=2\)這個命題第2個符號為\(+\)」這個命題即表示「\(0+1=2\)」這個命題可以被\(3^{11}\)整除但卻不能被\(3^{12}\)整除的意思。

邏輯表示：

\[\begin{aligned} (\exists x)(x \times 3^{11})\wedge \sim(\exists x)(x \times 3^{12}) \end{aligned}\]

哥德爾數表示：

(太長了就不寫了)
註：上面的\(3^{11}\)和\(3^{12}\)要先寫開來在寫成哥德爾數。

其它例子

如果現在有一個命題是「哥德巴赫猜想無法證明」這個命題可以寫為沒有任何一個證明過程以哥德巴赫猜想收尾，也就是不存在一個\(k\)步的證明過程，使他的哥德爾數能被\(k^{G}\)整除(\(G\)表示為哥德巴赫猜想的哥德爾數)。

哥德爾第一不完備定理

哥德爾第一不完備定理否定了希爾伯特計劃(Hilbert’s Program)中的完備性假設，任何自洽的形式系統，只要蘊涵皮亞諾算術公理，就可以在其中構造在體系中不能被證明的真命題，因此通過推理演繹不能得到所有真命題（即體系是不完備的）。證明如下：

定義

定義一個函數為\(sub(a,b,c)\)它的意思是取一個哥德爾數為\(a\)的那個命題，找到那個命題中哥德爾數為\(c\)這個符號的位置，把它替換成\(b\)，並且替換後那個命題的哥德爾數是\(sub(a,b,c)\)。

證明

現在考慮一個「無法證明哥德爾數是\(sub(y,y,17)\)」的命題，這個命題對應的哥德爾數是\(n\)。再考慮一個「無法證明哥德爾數是\(sub(n,n,17)\)」的命題:
1.取一個「無法證明哥德爾數是\(sub(y,y,17)\)」的命題
2.找到「無法證明哥德爾數是\(sub(y,y,17)\)」的命題，將其中的\(y\)替換成\(n\)
3.得到那就是一個「無法證明哥德爾數是\(sub(n,n,17)\)」的命題
也就是說「無法證明哥德爾數是\(sub(n,n,17)\)」的命題的哥德爾數正好就是\(sub(n,n,17)\)，這個結論也就表示自己這個命題是無法被證明的，顯然很奇怪。

分析

假設如果「無法證明哥德爾數是\(sub(n,n,17)\)」這個命題是假命題，我們可以知道這表示「可以證明哥德爾數是\(sub(n,n,17)\)」這個命題一定是真命題。而從這個真命題可以知道，只要哥德爾數是\(sub(n,n,17)\)的命題都可以被證明，那甚麼命題的哥德爾數是\(sub(n,n,17)\)呢？就是「無法證明哥德爾數是\(sub(n,n,17)\)」的這個命題。可以發現互相矛盾，因此原假設不成立，故「無法證明哥德爾數是\(sub(n,n,17)\)」這個命題是真命題。

結論

由公理出發，證明了真命題中有無法被證明的問題，因此希爾伯特計劃中的完備性是失敗的，因為數學問題不一定都可以證明。

數學邏輯符號