【數學理論】 10. 不完備、不一致、非保守、無法判定，數學信仰崩塌的過程 — 哥德爾不完備定理 (Gödel's Incompleteness Theorems)

--- title: 【數學理論】 10. 不完備、不一致、非保守、無法判定，數學信仰崩塌的過程 — 哥德爾不完備定理 (Gödel's Incompleteness Theorems) tags: - 【數學理論】 url: https://hackmd.io/@lewisjjj800/rkcL9IxMgx lastSync: 2025-05-25T08:46:05.185Z hackmd: url: https://hackmd.io/@lewisjjj800/rkcL9IxMgx title: 【數學理論】 10. 不完備、不一致、非保守、無法判定，數學信仰崩塌的過程 — 哥德爾不完備定理 (Gödel's Incompleteness Theorems) lastSync: 2025-05-25T08:52:33.472Z --- 不完備、不一致、非保守、無法判定，數學信仰崩塌的過程 === 哥德爾不完備定理 (Gödel's Incompleteness Theorems) ---  **庫爾特·弗雷德里希·哥德爾（Kurt Friedrich Gödel）**，出生於奧匈帝國，是美國數學家、邏輯學家和哲學家，維也納學派的成員。哥德爾是二十世紀最偉大的邏輯學家之一，絕對是大佬中的大佬。 1930年9月7日，年僅24歲的 **哥德爾 (Gödel)** 在柯尼斯堡舉行的**第二屆精確科學論會議**上聲稱，**希爾伯特的夢想我已經解決了**。 所有的數學家無不震驚，他們還在數學這塊大陸開墾時，怎麼一位24歲的年輕人橫空出世直接說他解決了呢！？ 哥德爾說：「**我已經證明數學是不完備的了。** 並且提出了「**哥德爾第一不完備定理 (Gödel's First Incompleteness Theorems)**」，證明了，在算術系統中，一定存在某些命題是真的，但是卻永遠無法證明。 從這一刻起，**數學信仰開始崩塌了**。 接下來我們展開說明什麼是**哥德爾第一不完備定理**。 --- ## 哥德爾數 (Gödel Number) 在 **哥德爾第一不完備定理**中，哥德爾利用**哥德爾數 (Gödel Number)** 構建了一種對應關係，把數學中的所有符號對應到一個個的數，這個數就是**哥德爾數 (Gödel Number)**。 >[!Note] **哥德爾數 (Gödel Number)** >**哥德爾數**把數學中的所有符號對應到一個個的數，也是一種編碼方式，這種編碼方式構建一種唯一的對應關係。 下面我們來看是如何**編碼**的。 | 符號 | 定義 | 編碼 | 符號 | 定義 | 編碼 |符號 | 定義 | 編碼 | |------|------|------|------|------|------|------|------|------| | $\neg$ | 非 | $1$ | $s$ | 後繼 | $7$ | $x$ | 變量 | $13$ | | $\lor$ | 或 | $2$ | $($ | 左括號 | $8$ | $y$ | 變量 | $17$ | | $\supset$ | 推論 | $3$ | $)$ | 右括號 | $9$ | $z$ | 變量 | $19$ | | $\exists$ | 存在 | $4$ | $,$ | 逗號 | $10$ | $\vdots$ | $\vdots$ | $\vdots$ | | $=$ | 等號 | $5$ | $+$ | 加號 | $11$ | $\vdots$ | $\vdots$ | $\vdots$ | | $0$ | 零 | $6$ | $\times$ | 乘號 | $12$ | **其他符號** | **變量** | **後繼質數** | > 上面表格中的**編碼**就是**哥德爾數**的意思哦！ 當然不只**符號**有哥德爾數，由**符號**構建出來的**命題**也有哥德爾數，命題的哥德爾數可以用算的，算法如下： 我們**考慮一個命題**： $$ 1+1=2 $$ 當我們想要算出這個**命題**的哥德爾數，那就要先轉換成**形式語言**，也就是用符號來表示。用符號表示 $1+1=2$ 就會是： $$ s0+s0=ss0 $$ > $s0$ 代表 $0$ **的後繼**，而 $0$ **的後繼**就是 $1$；$ss0$ 代表 $0$ **的後繼的後繼**，而 $0$ **的後繼**就是 $1$，所以 $0$ **的後繼的後繼**就是 $2$。以此類推，$10$ 用符號表示就是 $ssssssssss0$，代表 $0$ **的後繼的後繼的後繼的後繼的後繼的後繼的後繼的後繼的後繼的後繼**。 我們可以看到 $s0+s0=ss0$ 由左到右共有**九個符號**，把這九個符號由右至左排列如下： $$ s\space\space\space0\space\space\space+\space\space\space s \space\space\space0 \space\space\space= \space\space\space s \space\space\space s \space\space\space 0 $$ 透過上面**哥德爾編碼的表格**，我們可以知道 $=$、$0$、$s$、$+$ 的哥德爾數分別是 $5$、$6$、$7$、$11$。所以上面的排列就會是： $$ 6\space\space\space7\space\space\space11\space\space\space6\space\space\space7\space\space\space5\space\space\space6\space\space\space6\space\space\space7 $$ 接下來把上面那**九個數字由左到右塞到前九個相乘質數的指數位置上**： $$ 2^{\color{red}{6}}\times3^{\color{red}{7}}\times5^{\color{red}{11}}\times7^{\color{red}{6}}\times11^{\color{red}{7}}\times13^{\color{red}{5}}\times17^{\color{red}{6}}\times19^{\color{red}{6}}\times23^{\color{red}{7}} $$ 把上面的這些數字相乘完就會得到： \begin{array} 22^{6}\times3^{7}\times5^{11}\times7^{6}\times11^{7}\times13^{5}\times17^{6}\times19^{6}\times23^{7} \\ =22493787527614473314702266143065038083682741209375000000 \end{array} 因此，$1+1=2$ 這個命題的**哥德爾數**就是上面那一坨數字。 再舉幾個例子，上一篇我們介紹過的**皮亞諾公理**可以轉換成符號的表示方式如下： | 符號表示 | 意義 | |------|------| | $\exists$ $0$ | 存在自然數 $0$ | | $(\exists$ $x)(x=sy)$ | 存在自然數 $x$ 是自然數 $y$ 的後繼| | $\neg(sx=0)$ | 不存在後繼是 $0$ 的自然數 | | $(sx=sy)$$\supset$$(x=y)$ | 如果自然數 $x$ 與 $y$ 的後繼相等，那麼自然數 $x$ 等於 $y$ | 我們拿「**如果自然數** $x$ **與** $y$ **的後繼相等，那麼自然數** $x$ **等於** $y$ 」這個命題來算算他的哥德爾數。首先寫下這個命題的符號表示： $$ (sx=sy)\supset(x=y) $$ 我們可以看到 $(sx=sy)\supset(x=y)$ 由左到右共有**十三個符號**，把這十三個符號由右至左排列如下： $$ (\space\space\space s\space\space\space x\space\space\space = \space\space\space s \space\space\space y \space\space\space ) \space\space\space \supset \space\space\space ( \space\space\space x \space\space\space = \space\space\space y \space\space\space ) $$ 透過上面**哥德爾編碼的表格**，我們可以知道 $\supset$、$=$、$0$、$s$、$($、$)$、$x$、$y$ 的哥德爾數分別是 $3$、$5$、$6$、$7$、$8$、$9$、$13$、$19$。所以上面的排列就會是： $$ 8\space\space\space7\space\space\space13\space\space\space5\space\space\space7\space\space\space17\space\space\space9\space\space\space3\space\space\space8\space\space\space13\space\space\space5\space\space\space17\space\space\space9 $$ 接下來把上面那**十三個數字由左到右塞到前十三個相乘質數的指數位置上**： $$ 2^{8}\times3^{7}\times5^{13}\times7^{5}\times11^{7}\times13^{17}\times17^{9}\times19^{3}\times23^{8}\times29^{13}\times31^{5}\times37^{17}\times41^{9} $$ 把上面的這些數字相乘完就會得到一個有**139位數的數字**，這個數字就是「**如果自然數** $x$ **與** $y$ **的後繼相等，那麼自然數** $x$ **等於** $y$ 」這個命題的哥德爾數。 我們也可以把**皮亞諾公理**的其他命題轉換成哥德爾數： | 符號表示 | 哥德爾數 | |------|------| | $\exists$ $0$ | $2^{6}\times3^{6}$ | | $(\exists$ $x)(x=sy)$ | $2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{17}\times23^{9}$ | | $\neg(sx=0)$ | $2^{1}\times3^{8}\times5^{7}\times7^{13}\times11^{5}\times13^{6}\times17^{9}$ | 由此可知，命題的哥德爾數都很大。 你可能會想說：**怎麼那麼搞剛咧？** 但這種對應以及轉換的方法正是哥德爾數的精隨。 我們都學過 **質因數分解**，知道**算術基本定理 (Fundamental Theorem of Arithmetic)** >[!Important] **算術基本定理 (Fundamental Theorem of Arithmetic)** >又稱為正整數的**唯一分解定理**，即：「一個正整數的質因數分解是唯一的」**若且唯若**「一個正整數的每個分解皆可表示為相同質數的相同次方（除了順序不同以外）」。 也就是說，每個大於 $1$ 的自然數，要嘛本身就是質數，要嘛可以寫為2個或以上的質數的乘積，而**正整數分解為質數乘積的方式是唯一的，反之，質數乘積後的結果也是唯一的**。 因此，不會有兩個不同的質因數乘積結果是同一個正整數，也不會有一個正整數有兩種質因數分解方式。 因為命題的哥德爾數都是由**質因數**構成的，那根據**算術基本定理**，就可以確保**我們在計算每一個命題的哥德爾數時，每一個命題的哥德爾數都是唯一的**。相對的，我們拿到一坨數字進行質因數分解時，也能保證**分解完的結果不會剛好對應到其他命題**。 利用哥德爾數來描述命題還有一個好處是，我們在探討命題時，就能撇除掉一大堆中英文描述，將對**數學**的探討轉變成單純對**數字**進行探討。 這種將**語法轉變成數字**最大的好處是：它讓數學可以談論自己的語句與證明，用數字來「**看待數學本身**」。 而**哥德爾數**最強大的地方在於，各式各樣的命題都可以轉化成哥德爾數。 例如，我們考慮一個**錯的命題**： >[!Tip] **零不等於零** >$$ \neg (0=0) $$ 很顯然的，這個命題是錯的，但是錯的命題一樣可以轉換成**哥德爾數**：$$ 2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9} $$ 因此我們了解到，無論命題是對的還是錯的，我們都可以把這個命題轉換成**哥德爾數**。 你以為就這樣嗎？**一個「由命題構成」的命題**也可以計算**哥德爾數**，例如我們考慮一個由命題構成的命題： $$ \neg (0=0)\space 這個命題的第一個符號是\space \neg $$ 我們知道 $\neg (0=0)$ 這個命題的**哥德爾數**是：$$ 2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9} $$ 然而，$\neg$ 對應的**哥德爾數**是 $1$ ，而從左到右的 **第一個符號** 會被放在質因數的 $2$ 的指數位置，也就是 $2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9}$ 當中的 $2^{\color{red}{1}}$ 而 $2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9}$ 這個哥德爾數只有一個 $2^{1}$ 做為其因數，但如果 $\neg (0=0)$ 這個命題的開頭是用其他符號，例如： $\supset$ 做為開頭，$\supset$ 對應的哥德爾數是 $3$，那這個命題的哥德爾數就會有 $2^{\color{red}{3}}$ 做為其因數。 也就是說，**「$\neg (0=0)$ 這個命題的第一個符號是 $\neg$」** 這個命題可以被等價表示為：**「$\neg (0=0)$ 這個命題的哥德爾數可以被 $2^{1}$ 整除，卻不能被 $2^{2}$ 整除」** > 因為 $\neg$ 對應的**哥德爾數**是 $1$ ，其他符號則是 $2$、$3$、$4$、$5$...等等，而 $2^{2}$ 是 $2^{3}$、$2^{4}$、$2^{5}$ 這幾個數的因數，所以當任意一個命題的第一個符號是 $\neg$ ，就只能被 $2^{1}$ 整除而不能被 $2^{2}$ 整除。 那 **「$\neg (0=0)$ 這個命題的哥德爾數可以被 $2^{1}$ 整除，卻不能被 $2^{2}$ 整除」** 這個命題我們就可以用符號的方式寫出來： \begin{array} ((\exists \space x)(x\times2^{1}=2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9}) \\ \land \neg (\exists \space x)(x\times2^{2}=2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9}) \end{array} > 存在一個數 $x$ ，使得 $2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9}$ 可以被 $2^{1}$ 整除，且不存在一個數 $x$ ，使得 $2^{1}\times3^{8}\times5^{6}\times7^{5}\times11^{6}\times13^{9}$ 可以被 $2^{2}$ 整除。 上面的陳述都是符號，因此可以轉換成哥德爾數，但是這邊數字太大就不算了，就算算了也放不下... 根據上面幾個例子，我們知道可以把**符號**轉換成**哥德爾數**，由**符號**構成的**命題**也可以轉換成**哥德爾數**，而**由命題構成的命題**同樣可以轉換成**哥德爾數**，甚至**由「由命題構成的命題」構成的命題**一樣可以轉換成**哥德爾數**，無限嵌套下去也可以。 我們可以發現，**哥德爾數**將符號、語句、證明等語言結構，透過唯一的數字編碼，映射為自然數。因此只要是可以用符號（型式語言）表達的命題，我們都可以把「語法」和「證明過程」用哥德爾數——也就是**純粹的數字**來描述。 因為所有命題都能被以數字來表示，因此**我們能夠將一切命題利用「皮亞諾公理」來進行推導。** 現在我們對**哥德爾數**已經有一定的了解了，接下來我們就進入**不完備性的證明**。 --- ## 不完備性的證明現在我們都知道了，所有數學的命題（包括由命題構成的命題、由命題構成的命題構成的命題...）只要可以用符號來表示，那就可以轉換成**哥德爾數**。 因此，**哥德爾數**讓我們可以在「**皮亞諾公理**」裡面談論 **皮亞諾公理** 自己的語法與證明。 而這整個過程，從**哥德爾數**到建構命題再到論證，全部在**蘊含皮亞諾公理的形式系統**內完成。 此時我們必須先定義這邊提到的**蘊含皮亞諾公理的形式系統**，以下簡稱為**該形式系統**。 >[!Note] **該形式系統（蘊含皮亞諾公理的形式系統）** >須滿足以下條件： >- **包含足夠的算術基礎**：系統需要能夠表達和處理自然數的基本算術運算和性質，例如加法、乘法和序關係。這通常意味著系統至少包含羅賓遜算術（Robinson Arithmetic）或更強的系統如皮亞諾算術（Peano Arithmetic） >- **系統是一致的**：系統不能證明矛盾（即不能同時證明某陳述 $\phi$ 和其否定 $\neg \phi$）。 >- **系統是可遞歸公理化的**：公理集合必須是可計算的（recursively enumerable），即存在一個算法可以列出所有公理。 滿足以上這些條件的系統在數學和邏輯中非常常見，特別是在數論、集合論、計算理論和其他涉及算術的形式系統中。以下舉幾個常見的例子： >[!Note] **羅賓遜算數** >- 這是一個非常弱的算術系統，僅包含加法、乘法、後繼的基本公理，沒有完整的**歸納公理**。 >- 它已經滿足「足夠的算術基礎」，可以編碼證明過程，因此哥德爾不完備定理適用。 >[!Note] **皮亞諾公理** >- 是一個比**羅賓遜算術**還強的公理，包含完整的歸納公理，能表達更廣泛的數論陳述。 >- 它是研究數論的標準系統，廣泛應用於數學邏輯和計算理論。 >[!Note] **ZFC集合論** >- 是現代數學的基礎，幾乎能夠形式化所有的數學結構。 >- **ZFC集合論** 包含足夠的算術基礎（因為它可以定義自然數並模擬**皮亞諾公理**的運算），且通常假設一致並可遞歸公理化。 因此，後續只要提到**該形式系統**，就代表滿足上面說的那三個條件。 接下來，我們就開始來證明。 --- 首先我們再拿**皮亞諾公理**的其中一條來當一個**範例用的命題**： >[!Tip] **範例用的命題** >$$ (\exists \space x)(x=sy) \space \xrightarrow{代表}\ \space y\space有一個後繼 $$ 我們前面有算過這個命題的哥德爾數是： $$ 2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{17}\times23^{9} $$ 現在，我們來把上面這一坨數字記作 $m$ 。也就是：$$ m=2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{17}\times23^{9} $$ 因此，「$y$ **有一個後繼**」這個命題的**哥德爾數**現在記作 $m$。 接下來，我們來建構一種**替換**的過程。一樣用剛剛的範例： >[!Tip] **範例用的命題** >$$ (\exists \space x)(x=sy) \space \xrightarrow{代表}\ \space y\space有一個後繼 $$ 現在，我們讓 $m$ 來替換上面這個命題裡面的 $y$ ，那上面這個命題就會變成一個**新命題**： >[!Tip] **新命題** >$$ (\exists \space x)(x=sm) \space \xrightarrow{代表}\ \space m\space有一個後繼 $$ 因此，這個**新命題的哥德爾數**就會變成： $$ 2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{\color{red}{m}}\times23^{9} $$ > 其中 $m=2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{17}\times23^{9}$ 當然，還可以再繼續替換。 我們讓「$m$ **有一個後繼**」這個命題的**哥德爾數**記作 $k$ 用 $k$ 來替換上面這個命題裡面的 $m$ ，那上面這個命題就會又變成一個**新的新命題**： >[!Tip] **新的新命題** >$$ (\exists \space x)(x=sk) \space \xrightarrow{代表}\ \space k\space有一個後繼 $$ 現在，我們讓這個**具有替換過程的命題**的**哥德爾數**記作 $sub(a,b,c)$，並且把這個**具有替換過程的命題**訂為**命題一**： >[!Tip]**命題一**： >構建一個具有替換過程的命題，其構建過程如下： >1. 有一個哥德爾數 $a$ 他對應的命題是 $A$ 。 >2. 把哥德爾數 $c$ 轉換回對應的符號 $C$。 >3. 從 $A$ 中找到 $C$ 的位置，替換成 $b$。 > >**命題一**的哥德爾數定義成是 $sub(a,b,c)$ 拿剛剛的「$y$ **有一個後繼**」這個命題回顧一下替換過程： >[!Tip]**範例用的命題**： >$$ (\exists \space x)(x=sy) \space \xrightarrow{哥德爾數}\ \space m $$ ### 第一步：有一個哥德爾數 $a$ 他對應的命題是 $A$ 這邊的 $a$ 對應到 **範例用的命題** 中的 $m$，因為**範例用的命題**的哥德爾數是 $m$ 而 $A$ 則對應到原始的命題： $$ (\exists \space x)(x=sy) \space \xrightarrow{代表}\ \space y\space有一個後繼 $$ 所以**第一步**就會變成：**有一個哥德爾數 $m$ 他對應的命題是 $(\exists \space x)(x=sy)$ $\space \xrightarrow{代表}\ \space y\space有一個後繼$** ### 第二步：把哥德爾數 $c$ 轉換回對應的符號 $C$。這邊的 $c$ 對應到 $m=2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{\color{red}{17}}\times23^{9}$ ，也就是說現在的 $c$ 是 $17$ 。對應的符號 $C$ 則代表把 $17$ 對應回原本的**符號**，根據**哥德爾編碼**的表格，我們知道 $17$ 對應的是 $y$，因此對應的符號 $C$ 在這個範例對應的是 $y$。因此現在 $m$ 就會被替換成： $$ 2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{\color{red}{y}}\times23^{9} $$ > 注意，此時 $m$ 裡面 $19$ 的指數已經從 $17$ 被替換成 $y$ 了哦！ 所以**第二步**就會變成：**把哥德爾數 $17$ 轉換回對應的符號 $y$** ### 第三步：從 $A$ 中找到 $C$ 的位置，替換成 $b$ 剛剛我們知道，$A$ 對應的是原始的命題： $$ (\exists \space x)(x=sy) \space \xrightarrow{代表}\ \space y\space有一個後繼 $$ 對應的符號 $C$ 則代表把 $17$ 對應回原本的**符號** $y$ 最後 $b$ 則對應著 $m$，因為剛剛我們是想要用 $m$ 去替換掉 $y$ 所以**第三步**就會變成：從 $(\exists \space x)(x=sy)$ 這個命題中找到 $y$ 的位置，替換成 $m$。 --- 現在，我們回顧一下剛剛的構建過程： 1. 有一個哥德爾數 $m$ 他對應的命題是 $(\exists \space x)(x=sy)$ 。 2. 把哥德爾數 $17$ 轉換回對應的符號 $y$。 3. 從 $(\exists \space x)(x=sy)$ 中找到 $y$ 的位置，替換成 $m$。 所以這個構建出來的新命題就會是 $(\exists \space x)(x=sm)$ 那根據 **命題一**，新命題的**哥德爾數**就會是 $sub(m,m,17)$，其中： $$ sub(m,m,17)=2^{8}\times3^{4}\times5^{13}\times7^{9}\times11^{8}\times13^{5}\times17^{7}\times19^{m}\times23^{9} $$ > $sub(m,m,17)$ 其實就是剛剛的 $k$ 接著我們可以建立一個**命題二**，把**命題二**的哥德爾數記作 $n$： >[!Tip]**命題二**： >$$ 哥德爾數是 sub(y,y,17) 的命題無法被證明 \space \xrightarrow{哥德爾數}\ \space \space n $$ > $n$ 是把「哥德爾數是 $sub(y,y,17)$ 的命題無法被證明」這個命題經過哥德爾編碼計算過後的很大的數字。 現在我們考慮一個**命題三**： >[!Tip]**命題三**： >$$ 哥德爾數是 sub(n,n,17) 的命題無法被證明 $$ 那什麼是 **哥德爾數是 $sub(n,n,17)$ 的命題**呢？按照我們一開始對這個函數的定義，$sub(n,n,17)$ 可以理解成： 1. 有一個哥德爾數 $n$ 他對應的命題是「哥德爾數是 $sub(y,y,17)$ 的命題無法被證明」 2. 根據 $sub(n,n,17)$ 當中的 $17$，把哥德爾數 $17$ 轉換回對應的符號 $y$ 3. 從「哥德爾數是 $sub(y,y,17)$ 的命題無法被證明」中找到 $y$ 的位置，替換成 $n$ 所以「哥德爾數是 $sub(n,n,17)$ 的命題無法被證明」這個命題的哥德爾數就會變成： $$ sub(n,n,17) $$ 這樣**命題三**就會變成： >[!Tip]**命題三**： >$$ 哥德爾數是 sub(n,n,17) 的命題無法被證明 \space \xrightarrow{哥德爾數}\ \space sub(n,n,17) $$ 因為**命題三**的**哥德爾數是** $sub(n,n,17)$，我們可以發現，**命題三**就是：**哥德爾數是** $sub(n,n,17)$ **的命題**。 所以「**哥德爾數是 $sub(n,n,17)$ 的命題無法被證明**」這個命題就會變成：**命題三無法被證明**。 你發現了嗎？ **命題三**說的正是**自己無法被證明**。 --- 我們來探討一下**命題三**： >[!Tip]**命題三**： >$$ 哥德爾數是 sub(n,n,17) 的命題無法被證明 \space \xrightarrow{哥德爾數}\ \space sub(n,n,17) $$ 現在我們假設，**命題三**是一個假的命題： $$ 哥德爾數是 sub(n,n,17) 的命題無法被證明 \implies {\color{red}{假命題}} $$ 那就代表**命題三**的反面是一個真命題： $$ 哥德爾數是 sub(n,n,17) 的命題{\color{red}{可以}}被證明 \implies {\color{red}{真命題}} $$ 那什麼是 $哥德爾數是 sub(n,n,17) 的命題$ 呢？其實就是**命題三**，因此我們可以推論： $$ 哥德爾數是 sub(n,n,17) 的命題 \implies {\color{red}{真命題}} $$ >因為真命題才可以被證明 你發現了嗎？我們竟然從一個**假命題**，推導出這個**假命題**其實是一個**真命題**，矛盾了。 如果數學是**一致的**，就不應該存在**矛盾**，因此我們最一開始的假設： $$ 哥德爾數是 sub(n,n,17) 的命題無法被證明 \implies {\color{red}{假命題}} $$ <center>不成立！</center> 所以，**命題三**只能是一個真的命題： $$ 哥德爾數是 sub(n,n,17) 的命題無法被證明 \implies {\color{red}{真命題}} $$ **希爾伯特綱領**中的**完備性**告訴我們：「**所有真命題都能被證明**」 但是，我們卻從**該形式系統**中推導出**有一個真但是卻不能被證明的命題**，產生了**不完備**的情況。 這就是**哥德爾第一不完備定理 (Gödel's First Incompleteness Theorems)** >[!Important] **哥德爾第一不完備定理 (Gödel's First Incompleteness Theorems)** >任何**一致**的形式系統，只要蘊涵**皮亞諾公理**，就可以在其中構造在系統中不能被證明的真命題，因此通過推理演繹不能得到所有真命題，即：一致的**該形式系統是不完備的**。 --- ## 不一致性的證明我們回想一下剛剛證明的過程： 首先，我們從這個**該形式系統**中建構出一個**命題三**，而這個**命題三**代表著：「**我無法被證明**」 接著我們假設：如果數學是**一致的**，就不應該存在**矛盾**，因此**命題三**是一個真的命題： $$ 命題三：「我無法被證明」 \implies {\color{red}{真命題}} $$ 現在，我們來分兩種情況探討這個**命題三**。第一種情況是我們剛剛討論過的： ### 情況一、假如命題三無法被證明？假如**命題三**無法被證明，那就代表 **命題三：「我無法被證明」** 無法被證明。確實**命題三：「我無法被證明」** 是無法被證明的，所以這是一個真命題。但是！**命題三**是個真命題，我卻無法證明他！我們從**該形式系統**中推導出**有一個真但是卻不能被證明的命題**，產生了**不完備**的情況。 接下來我們看看第二種情況： ### 情況二、假如命題三可以被證明？假如**命題三**可以被證明，那就代表 **命題三：「我無法被證明」** 可以被證明。但是！**命題三：「我無法被證明」** 可以被證明的話，那就代表 **命題三無法被證明**！ <center>矛盾了！</center> 我們從**該形式系統**中推導出**可以被證明但是又不能被證明的命題**，產生了**不一致**的情況。 那現在我們構建一個命題來證明：**該形式系統**能夠證明自身是一致的。 接下來為求方便，**該形式系統** 先記作 $T$。 --- ### 第一步、構建命題 $G$ 首先我們知道，任何命題都可以用**哥德爾數**來表示，因此我們按照前面證明**哥德爾第一不完備定理**一樣，利用哥德爾數建構一個**真但是卻不能被證明的命題** $G$ （以下簡稱 $G$）： $$ G \space 無法在 \space T \space 中被證明。 $$ 也就是說，$G$ 是一個陳述，內容是「我無法從 **該形式系統** 中被證明出來」。向是前面提到的**命題三**。 用數學的方式表達就是： $$ G \equiv \neg \text{Prov}(G) $$ ### 第二步、推論現在我們定義，存在一個陳述 $\text{Con}(T)$，表示： $$ T \space 不會證明出矛盾的命題 $$ 這個陳述表示如下： $$ \text{Con}(T) \xrightarrow\ T \space 不會證明出矛盾的命題 $$ 當然這個陳述等價為： $$ \text{Con}(T) \xrightarrow\ T \space 是一致的 $$ 根據剛剛**哥德爾第一不完備定理**的推導結果，我們知道一致的**該形式系統會存在一個「真但是卻不能被證明的命題」**。 也就是說，如果 $T$ 是一致的，那 $G$ 是一個真但是不可證明的命題。 因此我們可以得到以下推論： $$ \text{Con}(T) \xrightarrow\ \neg \text{Prov}(G) $$ 但是回到第一步，我們知道： $$ G \equiv \neg \text{Prov}(G) $$ 因此我們可以得到以下推論： $$ \text{Con}(T) \xrightarrow\ G $$ ### 第三步、假設假設 $T$ 可以證明自己是一致的。也就是： $$ T \vdash \text{Con}(T) $$ ### 第四步、邏輯推論我們用反證法，檢查 **我們可以從** $T$ **中證明** $T$ **是一致的** 會導致什麼。 #### 步驟 1：檢查 $G$ 的性質我們知道，$G$ 這個命題代表：「我無法在 $T$ 中被證明。」 從上面這個陳述來看，如果 $T$ 可以證明 $G$，則 $T$ 可以證明「 $G$ 不可證」，但「$G$ 被證明」與「 $G$ 不可證」矛盾。 這意味著：如果 $T$ 可以證明 $G$，則 $T$ 證明了一個矛盾（ $G$ **可證** 且 $G$ **不可證**），所以 $T$ **不一致**。 反過來，現在我們有個假設是**我們可以從** $T$ **中證明** $T$ **是一致的**，那如果 $T$ 是一致的（即 $\text{Con}(T)$），則 $G$ 不可證（即 $T$ 無法證明 $G$）。 因此，在 $T$ 內，我們可以形式化**哥德爾第一不完備定理**的部分證明，得出「$T$ 是一致的」可以推論出「$G$ 不可證」，即： $$ \text{Con}(T) \xrightarrow\ G $$ #### 步驟 2：假設的推導剛剛我們說了，有個假設是**我們可以從** $T$ **中證明** $T$ **是一致的**，也就是 $T \vdash \text{Con}(T)$。 因為 $T \vdash \text{Con}(T)$ ，而且 $\text{Con}(T) \xrightarrow\ G$，所以： $$ T \vdash \text{Con}(T)\xrightarrow\ G $$ 那根據邏輯規則（若證明 $A \xrightarrow\ B$ 且證明 $A$，則證明 $B$），得出： $$ T \vdash G $$ 那 $G$ 又是什麼呢？ $G$ 就是在說：$G \space 無法在 \space T \space 中被證明$ 因此上面的推論可以等價為： $$ T \vdash \neg \text{Prov}(G) $$ 我們用 $T$ 證明了「$G$ 不可證」！代表可以證明一個不可被證明的命題，矛盾了！ ### 第四步、得出矛盾現在我們回想一下剛剛的過程。 首先我們定義一個 $G$ ： $$ G \space 無法在 \space T \space 中被證明。 $$ 而因為我們可以從$\text{Con}(T)$ 推論出 $G \space不可證$ (**哥德爾第一不完備定理**)，也就是： $$ \text{Con}(T) \xrightarrow\ G \equiv \neg \text{Prov}(G) $$ 接著我們假設了： $$ T \vdash \text{Con}(T) $$ 根據邏輯規則（若證明 $A \xrightarrow\ B$ 且證明 $A$，則證明 $B$），得出： $$ T \vdash G $$ 而上面這個陳述等價於： $$ T \vdash \neg \text{Prov}(G) $$ 也就是說，我們一開始假設**我們可以從** $T$ **中證明** $T$ **是一致的**，會推導出 $T$ 證明 $G$ 以及 $T$ 證明 $G \space不可證$。 但根據**哥德爾第一不完備性定理**，若 $T$ 是一致的，則 $T$ 無法證明 $G$，因為 $G$ 表示 $G \space 無法在 \space T \space 中被證明$，而一致的 $T$ 保證 $G$ 是真的。 - 我們推導出：$T$ 證明 $G$。 - 但是如果 $T$ 是一致的，根據**哥德爾第一不完備性定理**， $T$ 無法證明 $G$。上面這兩個結論不能同時成立。 因此，我們最一開始的假設 $T \vdash \text{Con}(T)$ **是錯誤的**。 ### 結論既然假設 $T \vdash \text{Con}(T)$ 會導致矛盾，我們得出： $$ 若\space T \space是一致的，則\space T \vdash \text{Con}(T) \space是錯誤的 $$ 也就是說，如果**該形式系統**是一致的話，那**該形式系統**無法證明自己是一致的。 這就是所謂的：**哥德爾第二不完備定理 (Gödel's Second Incompleteness Theorems)** >[!Important] **哥德爾第二不完備定理 (Gödel's Second Incompleteness Theorems)** >任何一致的形式系統，只要蘊涵皮亞諾公理，它就不能用於證明其本身的**一致性**。 --- ## 結論透過**哥德爾第一與第二不完備定理**，你發現了嗎？ 我們從這個數學系統中建構出一個**命題三**，而這個**命題三**代表著「**我無法被證明**」，那就表示： \begin{array} 如如果我能證明命題三 \implies 產生矛盾 \implies {\color{red}{數學系統不一致}}\\ 如果我不能證明命題三 \implies 命題三說的是真的但無法被證明 \implies {\color{red}{數學系統不完備}} \end{array} 因此，**哥德爾第一不完備定理**證明了：**蘊含皮亞諾公理的該形式系統**的**完備性**與**一致性**只能擇一，只要**蘊含皮亞諾公理的該形式系統**是**完備的**，就必定**存在矛盾**；而只要**蘊含皮亞諾公理的該形式系統**是**一致的**，就必定存在**真但卻無法被證明的情況**。 而且，**哥德爾第二不完備定理**證明了：只要一個**蘊含皮亞諾公理的該形式系統**是**一致的**，那我們也無法從**皮亞諾公理證明自己是一致的**。 這就好像是：**你是一位法官，國王給你的命令是這樣的：** >[!Caution] **國王的命令** >「凡是能確定有罪的嫌疑人，就該被**定罪**。 > 但如果**你誤判一個「其實無法確定是否有罪的人」為有罪**，那你就得陪葬。」 這時，一名嫌疑犯走進來，對你說： >[!Warning] **嫌疑犯** > **「嘿嘿！我剛才承認的犯罪事實都是真的—— > 但我要補一句：『我現在說的這句話是謊話。』」** 你卡住了。 - 如果你 **相信他說的話**，你就陷入了邏輯上的矛盾，無法確定他的話是真是假⇒ **不能定他罪。** - 如果你 **不相信他說的話**，你就沒有足夠的依據定他有罪 ⇒ **不能定他罪。** 所以你卡住了。 這位嫌疑犯就像**命題三**一樣： >[!Caution] **命題三** > 一旦你接受它，就引發**矛盾**； > 一旦你不接受它，它卻看起來是真的，卻又無法**證明**。 --- 所以，我們的數學系統其實是**不完美的**，我們不能同時確保一個**蘊含皮亞諾公理的形式系統**當中「**所有真命題都能被證明**」而且「**不引發任何矛盾**」。同時，我們也無法用**皮亞諾公理**證明一個**蘊含皮亞諾公理的形式系統**的一致性。 就這樣，我們理解了**希爾伯特綱領**中的漏洞，了解到數學系統無法同時具有**完備性**與**一致性**，而且無法自己證明自身的一致性。 你可能會想問：「那**希爾伯特綱領**中還有提到另外兩個：**保守性**以及**可判定性**呢？」 這個部分，我們保留到下一篇再來詳談。 我是Lewis，我們[**下一篇**](https://hackmd.io/@lewisjjj800/By1v9LlGle)專欄見！