數學/邏輯中的著名定理

哥德爾完備性定理

在以下內容中，我們陳述了定理的兩種等價形式，並展示了它們的等價性。

稍後，我們將證明定理。這將按照以下步驟進行

1. 將定理簡化為句子（沒有自由變數的公式）前束正規化，即所有量詞 ($\forall$ 和 $\exists$) 位於開頭。此外，我們將它簡化為第一個量詞是 $\forall$ 的公式。這是可能的，因為對於每個句子，都存在一個等價的句子，其前束正規化的第一個量詞是 $\forall$.
2. 將定理簡化為形式為 $\forall x_{1}\forall x_{2}...\forall x_{k}\exists y_{1}\exists y_{2}...\exists y_{m}\phi (x_{1}...x_{k},y_{1}...y_{m})$ 的句子。雖然我們不能簡單地透過重新排列量詞來做到這一點，但我們證明了證明這種形式的句子定理已經足夠了。
3. 最後，我們證明了這種形式的句子定理。
   • 這將透過首先注意到這樣的句子 $B=\exists x_{1}\exists x_{2}...\exists x_{k}\exists y_{1}\exists y_{2}...\exists y_{m}\phi (x_{1}...x_{k},y_{1}...y_{m})$ 要麼是可證偽的，要麼是在它成立的某個模型中存在；這個模型只是為構成 B 的子命題分配真值。這是由於命題邏輯的完備性，其中存在量詞不起作用。
   • 我們將這個結果擴充套件到更復雜和更長的句子，D_n（n=1,2...），它們從 B 建立起來，因此它們中的任何一個要麼是可證偽的，因此 φ 也是可證偽的，要麼它們都不是可證偽的，因此每個句子都在某個模型中成立。
   • 我們最後利用 D_n 成立的模型（如果它們都不可證偽）來構建一個 φ 成立的模型。

定理 1. 在所有結構中都成立的公式都是可證的。

這是完備性定理的最基本形式。我們立即將其重新表述為更適合我們目的的形式

定理 2. 每個公式 φ 要麼是可證偽的，要麼是在某個結構中可滿足的。

"φ 是可證偽的" 根據定義 意味著 "¬φ 是可證的"。

兩個定理的等價性

要檢視等價性，首先要注意，如果定理 1成立，並且 φ 在任何結構中都不可滿足，則 ¬φ 在所有結構中都成立，因此是可證的，因此 φ 是可證偽的，定理 2成立。另一方面，如果定理 2成立，並且 φ 在所有結構中都成立，則 ¬φ 在任何結構中都不可滿足，因此是可證偽的；然後 ¬¬φ 是可證的，因此 φ 也是可證的，因此定理 1成立。

定理 2 的證明：第一步

我們透過逐步限制需要證明 "φ 是可證偽的或可滿足的" 的所有公式 φ 的類別來證明定理 2。在開始時，我們需要證明所有可能的公式 φ 在我們的語言中都是如此。但是，假設對於每個公式 φ，都存在某個從更受限制的公式類別C中提取的公式 ψ，使得 "ψ 是可證偽的或可滿足的" → "φ 是可證偽的或可滿足的"。那麼，一旦這個斷言（在上一句話中表達）被證明，就只需要證明 "φ 是可證偽的或可滿足的" 對於屬於類別C的 φ 即可。還要注意，如果 φ 與 ψ 可證地等價（即，(φ≡ψ) 是可證的），那麼確實 "ψ 是可證偽的或可滿足的" → "φ 是可證偽的或可滿足的"（健全性定理需要證明這一點）。

存在標準技術可以將任意公式改寫成一個不使用函式或常量符號的公式，但需要引入額外的量詞；因此，我們將假設所有公式都不包含這些符號。在哥德爾的論文中，他使用了一個從一開始就沒有函式或常量符號的一階謂詞演算版本。

接下來，我們考慮一個通用的公式 φ（不再使用函式或常量符號），並將前束正規化定理應用於它，以找到一個正規化的公式 ψ，使得 φ≡ψ（ψ 處於正規化意味著，如果存在任何量詞，則所有量詞都位於 ψ 的開頭）。現在，我們只需要證明定理 2對於處於正規化的公式 φ 即可。

接下來，我們透過對所有自由變數進行存在量化來消除 φ 中的所有自由變數：如果，例如，x₁...x_n 是 φ 中的自由變數，我們形成 $\psi =\exists x_{1}...\exists x_{n}\phi$. 如果 ψ 在結構 M 中是可滿足的，那麼 φ 當然也是可滿足的；如果 ψ 是可證偽的，那麼 $\neg \psi =\forall x_{1}...\forall x_{n}\neg \phi$ 是可證的，那麼 ¬φ 也是可證的，因此 φ 是可證偽的。我們可以看到，我們可以將 φ 限制為一個句子，即一個沒有自由變數的公式。

最後，出於技術便利的原因，我們希望 φ 的字首（即 φ 開頭的一系列量詞，處於正規化）以一個全稱量詞開頭，以一個存在量詞結尾。為了在一個通用的 φ（受我們已經證明的限制）上實現這一點，我們使用 φ 中未使用的某個一元關係符號 F 和兩個新的變數 y 和 z。如果 φ = (P)Φ，其中 (P) 代表 φ 的字首，Φ 代表矩陣（φ 中剩餘的無量詞部分），我們形成 $\psi =\forall y(P)\exists z(\Phi \wedge [F(y)\vee \neg F(z)])$. 由於 $\forall y\exists z(F(y)\vee \neg F(z))$ 顯然是可證的，很容易看出 $\phi =\psi$ 是可證的。

將定理簡化為度為 1 的公式

我們通用的公式 φ 現在是一個句子，處於正規化，並且其字首以一個全稱量詞開頭，以一個存在量詞結尾。我們將所有此類公式的類稱為 R。我們需要證明的是 R 中的每個公式要麼是可證偽的，要麼是可滿足的。給定我們的公式 φ，我們將同一種類的量詞字串一起分組到塊中

$\phi =(\forall x_{1}...\forall x_{k_{1}})(\exists x_{k_{1}+1}...\exists x_{k_{2}}).......(\forall x_{k_{n-2}+1}...\forall x_{k_{n-1}})(\exists x_{k_{n-1}+1}...\exists x_{k_{n}})(\Phi )$

我們定義 $\phi$ 的度為 $\phi$ 矩陣中全稱量詞塊的數量，這些塊由存在量詞塊隔開，如上所示。以下引理，它是 Gödel 從 Skolem 對Löwenheim-Skolem 定理的證明中改編而來，使我們能夠大大降低需要證明定理的通用公式 $\phi$ 的複雜度

引理。設 k>=1。如果 R 中每個度為 k 的公式要麼是可證偽的，要麼是可滿足的，那麼 R 中每個度為 k+1 的公式也是如此。

評論：取一個形式為 $\phi =(\forall x)(\exists y)(\forall u)(\exists v)(P)\psi$ 的 k+1 度公式 φ，其中 $(P)\psi$ 是 $\phi$ 的剩餘部分（因此它具有 **k-1** 度）。φ 表明，對於每個 x，都存在一個 y，使得 ...（某事）。如果有一個謂詞 Q'，使得對於每個 x，Q'(x,y) 為真當且僅當 y 是使（某事）為真的所需的一個，那就太好了。然後我們可以寫一個與 φ 等價的 k 度公式，即 $(\forall x')(\forall x)(\forall y)(\forall u)(\exists v)(\exists y')(P)Q'(x',y')\wedge (Q'(x,y)\rightarrow \psi )$。這個公式確實與 φ 等價，因為它表明，對於每個 x，如果存在一個滿足 Q'(x,y) 的 y，則（某事）成立，此外，我們知道確實存在這樣的 y，因為對於每個 x'，都存在一個滿足 Q'(x',y') 的 y'。因此，φ 由此公式得出。同樣很容易證明，如果該公式為假，則 φ 也為假。不幸的是，通常情況下，不存在這樣的謂詞 Q'。但是，這個想法可以被理解為以下引理證明的基礎。

證明：令 φ 為一個 **k+1** 度公式；那麼我們可以將其寫為

$\phi =(\forall x)(\exists y)(\forall u)(\exists v)(P)\psi$

其中 **(P)** 是 $\phi$ 的字首的剩餘部分（因此它具有 **k-1** 度），而 $\psi$ 是 $\phi$ 的無量詞矩陣。**x**、**y**、**u** 和 **v** 在這裡表示變數的 *元組* 而不是單個變數；例如 $(\forall x)$ 實際上代表 $\forall x_{1}\forall x_{2}...\forall x_{n}$，其中 $x_{1}...x_{n}$ 是幾個不同的變數。

現在，令 **x'** 和 **y'** 為與 **x** 和 **y** 分別具有相同長度的先前未使用變數的元組，並令 **Q** 為先前未使用關係符號，其接受與 **x** 和 **y** 的長度之和相同的引數；我們考慮公式

$\Phi =(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )$

顯然，$\Phi \rightarrow \phi$ 是可證的。

現在，由於量詞串 $(\forall u)(\exists v)(P)$ 不包含來自 x 或 y 的變數，因此以下等價關係很容易用我們使用的任何形式化方法證明

$(Q(x,y)\rightarrow (\forall u)(\exists v)(P)\psi )\equiv (\forall u)(\exists v)(P)(Q(x,y)\rightarrow \psi )$

由於這兩個公式是等價的，如果我們將第一個公式替換為第二個公式，我們得到公式 Φ'，使得 Φ≡Φ'

$\Phi '=(\forall x')(\exists y')Q(x',y')\wedge (\forall x)(\forall y)(\forall u)(\exists v)(P)(Q(x,y)\rightarrow \psi )$

現在 Φ' 具有形式 $(S)\rho \wedge (S')\rho '$，其中 (S) 和 (S') 是某些量詞串，ρ 和 ρ' 是無量詞的，而且，此外，(S) 中的任何變數都不出現在 ρ' 中，(S') 中的任何變數都不出現在 ρ 中。在這種情況下，形式為 $(T)(\rho \wedge \rho ')$ 的任何公式，其中 (T) 是一個量詞串，包含 (S) 和 (S') 中的所有量詞，以任何方式交織在一起，但保持 (S) 和 (S') 中的相對順序，都將等價於原始公式 Φ'（這是我們依賴的一階謂詞演算中的另一個基本結果）。也就是說，我們將 Ψ 如下構造

$\Psi =(\forall x')(\forall x)(\forall y)(\forall u)(\exists y')(\exists v)(P)Q(x',y')\wedge (Q(x,y)\rightarrow \psi )$

我們有 $\Phi '\equiv \Psi$。

現在 $\Psi$ 是一個 **k** 次公式，因此根據假設，它要麼是可證偽的，要麼是可滿足的。如果 $\Psi$ 在一個結構 **M** 中是可滿足的，那麼，考慮到 $\Psi \equiv \Phi '\equiv \Phi \wedge \Phi \rightarrow \phi$，我們看到 $\phi$ 也是可滿足的。如果 $\Psi$ 是可證偽的，那麼 $\Phi$ 也是可證偽的，它等價於 $\Psi$；因此 $\neg \Phi$ 是可證明的。現在我們可以在可證明的公式 $\neg \Phi$ 中用其他依賴於相同變數的公式替換所有 Q 的出現。我們仍然會得到一個可證明的公式。（這是 一階謂詞演算 的另一個基本結果。根據對演算所採用的特定形式主義，它可以被看作是“函式替換”推理規則的簡單應用，如哥德爾的論文中所述，或者可以透過考慮 $\neg \Phi$ 的形式證明，在其中用具有相同自由變數的其他公式替換所有 Q 的出現，並注意到在替換後所有形式證明中的邏輯公理仍然是邏輯公理，並且所有推理規則仍然以相同的方式適用。)

在這個特定情況下，我們用公式 $(\forall u)(\exists v)(P)\psi (x,y|x',y')$ 替換 $\neg \Phi$ 中的 Q(x',y')。這裡 (x,y|x',y') 表示我們不是寫 ψ，而是寫了一個不同的公式，其中 x 和 y 被替換為 x' 和 y'。注意 Q(x,y) 被簡單地替換為 $(\forall u)(\exists v)(P)\psi$。

$\neg \Phi$ 然後變成

$\neg ((\forall x')(\exists y')(\forall u)(\exists v)(P)\psi (x,y|x',y')\wedge (\forall x)(\forall y)((\forall u)(\exists v)(P)\psi \rightarrow (\forall u)(\exists v)(P)\psi ))$

並且該公式是可以證明的；因為否定符號下和$\wedge$符號後面的部分顯然是可以證明的，而否定符號下和$\wedge$符號前面的部分顯然是φ，只是將x和y替換為x'和y'，我們看到$\neg \phi$是可以證明的，而φ是可證偽的。我們已經證明了φ要麼是可滿足的要麼是可證偽的，這結束了對引理的證明。

請注意，我們不能從一開始就使用$(\forall u)(\exists v)(P)\psi (x,y|x',y')$代替Q(x',y')，因為在這種情況下$\Psi$將不再是一個良構式公式。這就是為什麼我們不能天真地使用出現在證明之前的註釋中的論證。

證明關於度數為1的公式的定理

如上文引理所示，我們只需要證明關於R中度數為1的公式φ的定理。φ不可能是度數為0，因為R中的公式沒有自由變數並且不使用常數符號。因此，公式φ的一般形式為

$(\forall x_{1}...x_{k})(\exists y_{1}...y_{m})\phi (x_{1}...x_{k},y_{1}...y_{m})$

現在我們定義一個關於元組的自然數的k排序，如下：$(x_{1}...x_{k})<(y_{1}...y_{k})$應該成立，如果要麼$\Sigma _{k}(x_{1}...x_{k})<\Sigma _{k}(y_{1}...y_{k})$，要麼$\Sigma _{k}(x_{1}...x_{k})=\Sigma _{k}(y_{1}...y_{k})$，並且$(x_{1}...x_{k})$在字典序中先於$(y_{1}...y_{k})$。[這裡$\Sigma _{k}(x_{1}...x_{k})$表示元組的項之和。] 將此排序中的第n個元組表示為$(a_{1}^{n}...a_{k}^{n})$。

將公式 $B_{n}$ 設定為 $\phi (z_{a_{1}^{n}}...z_{a_{k}^{n}},z_{(n-1)m+2},z_{(n-1)m+3}...z_{nm+1})$。然後將 $D_{n}$ 設定為

$(\exists z_{1}...z_{nm+1})(B_{1}\wedge B_{2}...\wedge B_{n})$

引理：對於每個 n，$\phi \rightarrow D_{n}$。

證明：用數學歸納法證明 n；我們有 $D_{k}\equiv D_{k-1}\wedge (\exists z_{1}...z_{nm+1})B_{n}\equiv D_{k-1}\wedge (\exists z_{a_{1}^{n}}...z_{a_{k}^{n}})(\exists y_{1}...y_{m})\phi (z_{a_{1}^{n}}...z_{a_{k}^{n}},y_{1}...y_{m})$，其中後面的等價關係成立是因為變數替換，因為元組的排序使得 $(\forall k)({a_{1}^{n}}...{a_{k}^{n}})<(n-1)m+2$。這裡的每個合取項顯然都來自 φ。

對於基本情況，$D_{1}\equiv (\exists z_{1}...z_{m+1})\phi (z_{a_{1}^{1}}...z_{a_{k}^{1}},z_{2},z_{3}...z_{m+1})\equiv (\exists z_{1}...z_{m+1})\phi (z_{1}...z_{1},z_{2},z_{3}...z_{m+1})$ 顯然也是 φ 的推論。因此，引理 得證。

現在，如果對於某個n，$D_{n}$ 是可證偽的，那麼 φ 也是可證偽的。另一方面，假設對於任何n，$D_{n}$ 都是不可證偽的。那麼，對於每個n，都有一種方法可以將真值分配給不同的子命題 $E_{h}$（按其在$D_{n}$ 中首次出現的順序排列；這裡“不同”是指不同的謂詞，或不同的繫結變數）在$B_{k}$ 中，使得當每個命題以這種方式評估時，$B_{k}$ 為真。這是由基礎命題邏輯 的完備性推出的。

現在我們將證明，存在這樣一種對$E_{h}$ 的真值分配，使得所有$D_{n}$ 都是真的：$E_{h}$ 在每個$D_{n}$ 中以相同的順序出現；我們將透過一種“多數投票”的方式歸納定義對它們的通用分配：由於有無限多種分配影響$E_{1}$，要麼有無限多種分配使$E_{1}$ 為真，要麼有無限多種分配使它為假，而只有有限多種分配使它為真。在前一種情況下，我們選擇$E_{1}$ 在一般情況下為真；在後一種情況下，我們選擇它在一般情況下為假。然後，從無限多種使$E_{1}throughE_{h-1}$ 被分配與一般分配中相同的真值的n 中，我們以相同的方式選擇對$E_{h}$ 的通用分配。

這個一般賦值必須導致每個$B_{k}$ 和 $D_{k}$ 都為真，因為如果其中一個 $B_{k}$ 在一般賦值下為假，則對於所有n > k，$D_{n}$ 也將為假。但這與以下事實相矛盾：對於 $D_{k}$ 中出現的有限的一般 $E_{h}$ 賦值集合，存在無限多個n，其中使$D_{n}$ 為真的賦值與一般賦值相匹配。

現在，從這個使所有 $D_{k}$ 為真的賦值出發，我們構建語言謂詞的解釋，使得 φ 為真。模型的宇宙將是自然數。每個 i 元謂詞 $\Psi$ 應該對自然數 $(u_{1}...u_{i})$ 為真，當且僅當命題 $\Psi (z_{u_{1}}...z_{u_{i}})$ 在一般賦值中為真，或者它未被賦值（因為它從未出現在任何 $D_{k}$ 中）。

在這個模型中，每個公式 $(\exists y_{1}...y_{m})\phi (a_{1}^{n}...a_{k}^{n},y_{1}...y_{m})$，根據構造為真。但這意味著 φ 本身在模型中為真，因為 $a^{n}$ 遍歷所有可能的自然數 k 元組。所以 φ 是可滿足的，我們完成了。

直觀解釋

我們可以將每個 B_i 寫成 Φ(x₁...x_k,y₁...y_m)，其中一些 x 可以稱為“第一個引數”，一些 y 可以稱為“最後一個引數”。

以 B₁ 為例。它的“最後一個引數”是 z₂,z₃...z_m+1，對於這些變數中 k 個變數的每種可能組合，都存在某個 j 使得它們作為“第一個引數”出現在 B_j 中。因此，對於足夠大的 n₁，D_n1 具有這樣的性質：B₁ 的“最後一個引數”以它們中每種可能的 k 個組合形式，作為“第一個引數”出現在 D_n 中的其他 B_j 中。對於每個 B_i，都存在一個具有相應性質的 D_ni。

因此，在滿足所有 D_n 的模型中，存在對應於 z₁、z₂... 的物件，並且這些物件的每個 k 個組合都以“第一個引數”的形式出現在某個 B_j 中，這意味著對於這些物件的每個 k 個 z_p1...z_pk，都存在 z_q1...z_qm 使得 Φ(z_p1...z_pk,z_q1...z_qm) 成立。透過取僅包含這些 z₁、z₂... 物件的子模型，我們得到一個滿足 φ 的模型。

哥德爾不完備定理

第一定理：對於任何一致的正式、可計算列舉的理論，該理論證明了基本的算術真理，可以構造一個在該理論中不可證明但為真的算術命題。也就是說，任何能夠表達基本算術的有效生成的理論都不可能同時既一致又完備。

第二定理：對於任何包含基本算術真理以及關於形式可證性的某些真理的正式遞迴可列舉（即有效生成的）理論 T，T 包含其自身一致性的陳述當且僅當 T 不一致。

現代證明

假設存在一臺計算機，並且形式邏輯可以表示為計算機程式，那麼從計算機科學的基本引理中很容易證明哥德爾不完備定理。

1. 奎因引理—任何計算機程式都可以包含一個子程式，該子程式會打印出整個程式的程式碼。這允許任何程式將自身寫入字串變數，或寫入足夠大的大整數。

證明：讓列印子程式是一個標準的奎因，幷包含包含所有其餘程式碼的附加資料。

2. 停機問題引理：不存在一個計算機程式PREDICT(P)，它接受程式P的程式碼，並預測P是否最終會停機。

證明：編寫程式SPITE，它將自身列印到變數 R 中，然後計算PREDICT(R)。如果答案是R 會停機，那麼 Spite 進入一個無限迴圈。如果答案是R 不會停機，那麼SPITE 停機。由於 R 實際上是偽裝的SPITE，所以無論PREDICT說什麼，答案都是錯誤的。

不完備定理：假設一個公理系統描述了整數（或任何其他離散結構），並且它具有足夠的操作（加法和乘法就足夠了）來描述計算機的工作。那麼該系統要麼不一致，要麼不完備。

證明：編寫DEDUCE 來推匯出公理系統的全部結果。讓DEDUCE 將其自身的程式碼列印到變數 R 中，並在系統內部的計算機嵌入中搜索定理R 永遠不會停機。只有當DEDUCE 找到這個定理時，它才會停機。

如果公理系統證明了DEDUCE 不會停機，那麼它是不一致的。如果該系統是一致的，那麼DEDUCE 不會停機，並且公理無法證明它。

這個論證並沒有明確地證明不完備性，因為一個一致的公理系統仍然可以證明$\omega$-不一致定理，即DEDUCE 會停機（即使它沒有停機），而且沒有矛盾。

所以編寫ROSSER：ROSSER 將其程式碼列印到 R 中，並在推論中搜索 1. R 列印了一些內容或 2. R 從未列印過任何內容。如果它找到了 1，那麼它會在不列印任何內容的情況下停機。如果它找到了 2，那麼它會向螢幕列印 "Hello World!" 並停機。

如果公理系統是一致的，那麼它既不能證明ROSSER 最終會列印一些內容，也不能證明其否定ROSSER 不會列印任何內容。所以，無論它關於DEDUCE 的結論是什麼，公理系統都是不完備的。

為了證明第二個不完備定理，請注意，公理的一致性證明了DEDUCE 不會停機，所以公理系統不能證明其自身的一致性。