數理邏輯筆記 No.4

Veröffentlicht am in . Aufrufe:
Gödel's incompleteness theorems; Turing machine.

上一篇: 形式算術和遞歸函數

Gödel 不完備性定理

不完備性定理

Gödel 第一不完備性定理

$K_N$ 中公式集 $\Gamma$ 是完備的, 是指對 $K_N$ 中任一閉式 $p$, $\Gamma\vdash p$ 和 $\Gamma\vdash\neg p$ 必居其一. Gödel 第一不完備性定理斷言, $K_N$ 的公理集 $\mathcal{N}$ 是不完備的. 為證明這個結論, 只需構造出一個閉式, 它是 $\mathcal{N}$ 不可判定的, 即 $\Gamma\not\vdash p$ 且 $\Gamma\not\vdash\neg p$.

由上一篇的分析可知, $K_N$ 上的結論可以通過 Gödel 配數轉化為關於自然數的結論, 而關於自然數的結論又可在 $K_N$ 中形式化. 利用兩個層次間的關聯及轉化, 構造出一種具有 “自相關” 特徵的公式, 這就是 Gödel 證明的核心.

首先引入 “$\omega$ -無矛盾” 的概念, 這是一個比 “無矛盾” 更強的條件.

公式集 $\Gamma$ 是 $\omega$ -無矛盾的, 意為對 $K_N$ 中任一含自由變元的公式 $p(x)$, 以下兩條不同時成立:

  1. 對所有 $n\in\mathbb{N}$, $\Gamma\vdash p(\overline{n})$;
  2. $\Gamma\vdash\neg\forall x\thinspace p(x)$.

接下來開始構造具有 “自相關” 形式的公式.

定義二元關係 $W$: $(n_1,n_2)\in W$ $\Leftrightarrow$ $n_1$ 是某個公式 $p(x_1)$ 的 Gödel 數, $n_2$ 是 $p(\overline{n_1})$ 從 $\mathcal{N}$ 的證明的 Gödel 數. 換一種寫法, 即
$$(n_1,n_2)\in W\enspace\Leftrightarrow\enspace n_1\in\text{FM}\wedge(\text{Sub}(2^{15+2},\text{Num}(n_1),n_1),n_2)\in\text{PRF}$$
由 $\text{FM}$, $\text{Sub}$, $\text{Num}$, $\text{PRF}$ 的遞歸性可得二元關係 $W$ 的遞歸性, 從而 $W$ 在 $K_N$ 中可表示. 設 $W$ 用公式 $w(x_1,x_2)$ 可表示:
$$
\begin{align*}
(n_1,n_2)\in W \enspace &\Rightarrow \enspace \mathcal{N}\vdash w(\overline{n_1},\overline{n_2}) \\
(n_1,n_2)\not\in W \enspace &\Rightarrow \enspace \mathcal{N}\not\vdash w(\overline{n_1},\overline{n_2})
\end{align*}
$$
記
$$\text{p}(x_1)=\forall x_2\thinspace \neg w(x_1,x_2)$$
它只含一個自由變元 $x_1$. 令 $m=\text{g}(\text{p}(x_1))$, 用 $\overline{m}$ 去替換 $\text{p}(x_1)$ 中所有自由出現的 $x_1$, 得一閉式:
$$\text{p}(\overline{m})=\forall x_2\thinspace \neg w(\overline{m},x_2)$$
該公式的直觀含義是: 對任何自然數 $n$, 都有 $(m,n)\not\in W$, 而 $m$ 正是 $\text{p}(x_1)$ 的 Gödel 數. 所以, 公式 $\text{p}(\overline{m})$ 斷言, 不存在自然數 $n$, 使得 $n$ 成為 $\text{p}(\overline{m})$ 從 $\mathcal{N}$ 的證明的 Gödel 數, 換句話說, $\text{p}(\overline{m})$ 斷言其自身不可證. (注意 $W$ 的定義)

Gödel 第一不完備性定理:

  1. 若 $\mathcal{N}$ 無矛盾, 則 $\mathcal{N}\not\vdash\text{p}(\overline{m})$,
  2. 若 $\mathcal{N}$ $\omega$ -無矛盾, 則 $\mathcal{N}\not\vdash\neg\text{p}(\overline{m})$.

假設 $\mathcal{N}\vdash\text{p}(\overline{m})$, 即 $\mathcal{N}\vdash\forall x_2\thinspace \neg w(\overline{m},x_2)$, 則有 $\mathcal{N}\vdash\neg w(\overline{m},\overline{n})$.
把 $\text{p}(\overline{m})$ 從 $\mathcal{N}$ 的一個證明的 Gödel 數記為 $n$, 則 $(m,n)\in W$. 因 $W$ 用 $w(x_1,x_2)$ 可表示, 所以 $\mathcal{N}\vdash w(\overline{m},\overline{n})$, 於是可得 $\mathcal{N}$ 是有矛盾的.

假設 $\mathcal{N}\vdash\neg\text{p}(\overline{m})$, 即 $\mathcal{N}\vdash\neg\forall x_2\thinspace \neg w(\overline{m},x_2)$. 由於已知 $\mathcal{N}\vdash\text{p}(\overline{m})$ 不成立, 所以根據 $W$ 的定義可知, 對任意自然數 $n$ 都有 $(m,n)\not\in W$, 即對任意 $n$ 都有 $\mathcal{N}\vdash\neg w(\overline{m},\overline{n})$, 這表明 $\mathcal{N}$ 不是 $\omega$ -無矛盾的. $\square$

Gödel-Rosser 定理

上一節在 $\omega$ -無矛盾的條件下證明了 $\mathcal{N}$ 的不完備性, 但這個更強的條件其實是不必要的. Gödel-Rosser 定理就是僅在 “無矛盾” 的假定下證明了 $\mathcal{N}$ 的不完備性.

Gödel-Rosser 定理:
$\mathcal{N}$ 的任何遞歸無矛盾擴張 $\mathcal{N}^{*}$ 都不完備. 即, 如果擴張的公理集 $\mathcal{N}^{*}$ 無矛盾, 且 $\text{PA}^{*}$ ($\mathcal{N}^{*}$ 中全部公理的 Gödel 數構成的集) 是遞歸集, 那麼 $\mathcal{N}^{*}$ 不完備.

把 $\text{PF}$ 和 $\text{PRF}$ 定義式 (參見上一篇) 中的 $\mathcal{N}$ 改為 $\mathcal{N}^{*}$, 這不改變 $\text{PF}$ 和 $\text{PRF}$ 的遞歸性.

作二元關係 $W$ 和 $W^{*}$:
$(n_1,n_2)\in W$ $\Leftrightarrow$ $n_1$ 是某個公式 $p(x_1)$ 的 Gödel 數, $n_2$ 是 $p(\overline{n_1})$ 從 $\mathcal{N}^{*}$ 的證明的 Gödel 數.
$(n_1,n_2)\in W^{*}$ $\Leftrightarrow$ $n_1$ 是某個公式 $p(x_1)$ 的 Gödel 數, $n_2$ 是 $\neg p(\overline{n_1})$ 從 $\mathcal{N}^{*}$ 的證明的 Gödel 數.

則 $W$ 仍是遞歸的. $W^{*}$ 也是遞歸的, 因為其特徵函數滿足
$$C_{W^{*}}(n_1,n_2)=C_{\text{FM}}(n_1)\times C_{\text{PRF}}(\text{Sub}(2^{15+2},\text{Num}(n_1),2^7 * n_1),n_2)$$

設 $W$ 和 $W^{*}$ 分別用 $w(x_1,x_2)$ 和 $w^{*}(x_1,x_2)$ 可表示. 記
$$\text{p}(x_1)=\forall x_2\left(w(x_1,x_2)\to\exists y(y\leq x_2 \wedge w^{*}(x_1,y))\right)$$
其中 $y$ 取不在 $w(x_1,x_2)$ 和 $w^{*}(x_1,x_2)$ 中出現的某個變元. 令 $m=\text{g}(\text{p}(x_1))$, 則:
$$\text{p}(\overline{m})=\forall x_2\left(w(\overline{m},x_2)\to\exists y(y\leq x_2 \wedge w^{*}(\overline{m},y))\right)$$
直觀上, $\text{p}(\overline{m})$ 斷言, 若其自身從 $\mathcal{N}^{*}$ 可證, 那麼其否定就也從 $\mathcal{N}^{*}$ 可證且證明更簡單 (對應 Gödel 數更小).

容易從 $\mathcal{N}^{*}\vdash \text{p}(\overline{m})$ 和 $\mathcal{N}^{*}\vdash\neg\text{p}(\overline{m})$ 中分別推出矛盾, 從而在 $\mathcal{N}^{*}$ 無矛盾的前提下證明 $\mathcal{N}^{*}\not\vdash \text{p}(\overline{m})$ 且 $\mathcal{N}^{*}\not\vdash\neg\text{p}(\overline{m})$, 即 $\mathcal{N}^{*}$ 是不完備的. $\square$

但由此不能得出: $\mathcal{N}$ 的任何無矛盾擴張都不可能完備. 例如, 可以仿照證明 $K$ 的完全性時的做法, 在保證無矛盾的前提下遍歷 $K_N$ 的所有閉式, 歸納地定義出一串 $\mathcal{N}$ 的無矛盾擴張, 最後將這些擴張全都並起來得到 $\Gamma^{*}$. 若把 $\Gamma^{*}$ 作為擴張的算術公理集, 我們就達到了完備化. 但是, 由 Gödel-Rosser 定理, $\Gamma^{*}$ 中公理的 Gödel 數集必是非遞歸的, 故由 Church 論題, 不存在算法可用來確定任給的公式是不是 $\Gamma^{*}$ 中的公理, 也不存在算法可用來確定任給的有限公式序列是不是從 $\Gamma^{*}$ 的證明.

把所有在 $\mathbb{N}$ 中恆真的 $K_N$ 的公式構成的集記作 $\text{Tr}$, 則 $\text{Tr}$ 也是 $\mathcal{N}$ 的無矛盾完備擴張. 但是由 Gödel-Rosser 定理, $\text{Tr}$ 中公式的 Gödel 數構成的集 $\text{TR}$ 必是非遞歸的.

總之, 任何把 Peano 形式算術包含在內的數學形式系統, 只要有算法能用來確定該系統的任一篇文章 (公式的有限序列) 是不是一個證明 (這時說該系統是 “遞歸可公理化” 的), 這樣的系統一定不完備.

Gödel 第二不完備性定理

20世紀20年代初, Hilbert 提出了著名的有窮主義綱領, 其核心是要證明包含無窮的經典數學能夠幫助我們獲得關於具體, 有限事物的知識, 而這種證明方法自身必須是無疑議的. 為此, Hilbert 構建了原始遞歸算術 ($\text{PRA}$), 其中只包含原始遞歸函數, 於是目標就轉變為證明 Peano 算術 ($\text{PA}$) 相對於 $\text{PRA}$ 的保守性 (即對 $\text{PRA}$ 中任何公式 $\varphi$, 若 $\text{PA}\vdash\varphi$, 則 $\varphi$ ), 而保守性又可進一步歸約為 $\text{PA}$ 的無矛盾性. 所以 Hilbert 綱領的目標最終歸結為: 在 $\text{PRA}$ 中證明 $\text{PA}$ 的無矛盾性 (把這裡的 $\text{PA}$ 換成比方說 $\text{ZFC}$, 就可以使綱領涵蓋更多數學領域, 而不僅僅是算術). 然而, Gödel 的第二不完備性定理否定了這個可能, 從而在一定程度上否定了 Hilbert 的有窮主義綱領.

Gödel 第二不完備性定理斷言: 如果包括初等數論在內的數學形式系統是無矛盾的, 那麼這種無矛盾性就不可能在此系統中得到證明. 下面就形式系統 $K_N$ 證明第二不完備性定理的一種易證形式. 其證明需要把第一定理前半部分的證明在系統中再次形式化.

我們已經知道, 二元關係
$$\text{PRF}=\lbrace(n_1,n_2):n_1=\text{g}(q), n_2 \thinspace 是 \thinspace q \thinspace 從 \thinspace \mathcal{N} \thinspace 的證明的 \thinspace \text{Gödel} \thinspace 數 \thinspace \rbrace$$
是遞歸的. 設 $\text{PRF}$ 用公式 $\text{prf}(x_1,x_2)$ 可表示, 記 $\text{pr}(x_1)=\exists x_2\thinspace\text{prf}(x_1,x_2)$.

下面先證明兩個引理.

第一可推性條件: 對任一公式 $q$,
$$\mathcal{N}\vdash q\enspace\Rightarrow\enspace\mathcal{N}\vdash\text{pr}(\ulcorner q\urcorner)$$
其中 $\ulcorner q\urcorner$ 是 $\overline{\text{g}(q)}$ 的簡寫.

證明: 記 $m=\text{g}(q)$, 則 $\overline{m}=\ulcorner q\urcorner$. 設 $n$ 是 $q$ 從 $\mathcal{N}$ 的一個證明的 Gödel 數, 則 $(m,n)\in\text{PRF}$, 進而有 $\mathcal{N}\vdash\text{prf}(\overline{m},\overline{n})$.
由此使用 $\exists_1$ 規則 (見筆記第2篇) 便得 $\mathcal{N}\vdash\exists x_2\thinspace\text{prf}(x_1,x_2)$, 即 $\mathcal{N}\vdash\text{pr}(\ulcorner q\urcorner)$. $\square$

可推性條件

既然有第一可推性條件, 那麼自然有另外的可推性條件:
$$
\begin{align*}
&(D1)\quad \mathcal{N}\vdash q\enspace\Rightarrow\enspace\mathcal{N}\vdash\text{pr}(\ulcorner q\urcorner)\\
&(D2)\quad \mathcal{N}\vdash \text{pr}(\ulcorner q\urcorner)\to \text{pr}(\ulcorner \text{pr}\left(\ulcorner q\urcorner)\urcorner\right) \\
&(D3)\quad \mathcal{N}\vdash\text{pr}(\ulcorner q\to r\urcorner)\to(\text{pr}(\ulcorner q\urcorner)\to\text{pr}(\ulcorner r\urcorner))
\end{align*}
$$
這三條統稱為 Löb 證明條件, 其作用是在系統內再次形式化第一不完備性定理的證明. 它們把握了證明第二不完備性定理的全部條件, 但後兩條在這個對易證形式的證明當中是不必要的.

遞歸函數 $\text{Num}$ 和 $\text{Sub}$ 分別滿足: (具體定義參見上一篇)
$$
\begin{align*}
&\text{Num}(n) = \text{g}(\overline{n}) \\
&\text{Sub}(\text{g}(x_i),\text{g}(t),\text{g}(p(x_i))) = \text{g}(p(t))
\end{align*}
$$
用 $\text{Num}$ 和 $\text{Sub}$ 定義一個新的二元遞歸函數 $\text{Su}$:
$$\text{Su}(n_1,n_2)=\text{Sub}\left(\text{g}(x_1),\text{Num}(n_1),n_2\right)$$
其中 $\text{g}(x_1)=2^{15+2}$. 則 $\text{Su}$ 滿足
$$\text{Su}(n_1,\text{g}(p(x_1)))=\text{g}(p(\overline{n_1}))$$
設 $\text{Su}$ 用公式 $\text{su}(x_1,x_2,y)$ 可表示.

對角線引理: 對任一以 $x_1$ 為僅有的自由變元的公式 $p(x_1)$, 必存在閉式 $q_0$ 滿足:
$$\mathcal{N}\vdash q_0\leftrightarrow p(\ulcorner q_0\urcorner)$$
我們把具有這種性質的 $q_0$ 叫做公式 $p(x_1)$ 的不動點.

證明: 記
$$
\begin{align*}
&r(x_1) = \exists y(p(y)\wedge\text{su}(x_1,x_1,y)), \\
&m = \text{g}(r(x_1)), \\
&q_0 = r(\overline{m}), \\
&k = \text{g}(q_0).
\end{align*}
$$
則 $q_0$ 即為所要求的不動點.

顯然, 我們有 $q_0=r(\overline{m})=\exists y(p(y)\wedge\text{su}(\overline{m},\overline{m},y))$, 又根據 $\text{Su}$ 的定義, $\text{Su}(m,m)=\text{g}(r(\overline{m}))=k$, 所以
$$
\begin{aligned}
q_0 & \Leftrightarrow \exists y(p(y)\wedge y\approx \overline{k}) \\
& \Leftrightarrow \exists y(p(y)\wedge y\approx \ulcorner r(\overline{m})\urcorner) \\
& \Leftrightarrow \exists y(p(y)\wedge y\approx \ulcorner q_0\urcorner) \\
& \Leftrightarrow p(\ulcorner q_0\urcorner)
\end{aligned}
$$
其中, 最後一行的 $\Rightarrow$ 使用了 $\exists_2$ 規則. $\square$

定義一個新的二元關係 $\text{PRF}^{*}$:
$$\text{PRF}^{*}=\lbrace(n_1,n_2):n_1=\text{g}(q), n_2 \thinspace 是 \thinspace \text{pr}(\overline{n_1})\to\neg q \thinspace 從 \thinspace \mathcal{N} \thinspace 的證明的 \thinspace \text{Gödel} \thinspace 數 \thinspace\rbrace$$
易證 $\text{PRF}^{*}$ 是遞歸的.

設 $\text{PRF}^{*}$ 用公式 $\text{prf}^{*}(x_1,x_2)$ 可表示, 記
$$\text{pr}^{*}(x_1)=\exists x_2\thinspace\text{prf}^{*}(x_1,x_2)$$
引入記號 $\text{con}_{\mathcal{N}}$:
$$\text{con}_{\mathcal{N}}=\forall x_1\neg(\text{pr}(x_1)\wedge\text{pr}^{*}(x_1))$$
$\text{con}_{\mathcal{N}}$ 成立意味著任何公式 $q$ 都不會使 $\mathcal{N}\vdash q$ 和 $\mathcal{N}\vdash\text{pr}(\ulcorner q\urcorner)\to\neg q$ 同時成立, 根據第一可推性條件, 這也就意味著, 任何公式 $q$ 都不會使 $\mathcal{N}\vdash q$ 和 $\mathcal{N}\vdash\neg q$ 同時成立. 所以公式 $\text{con}_{\mathcal{N}}$ 的直觀意思就是: $\mathcal{N}$ 無矛盾.

現考慮公式 $\text{pr}(x_1)\to\text{pr}^{*}(x_1)$, $x_1$ 是其唯一的自由變元, 所以由對角線引理, 該公式有不動點 $q_0$:
$$\mathcal{N}\vdash q_0\leftrightarrow(\text{pr}(\ulcorner q_0\urcorner)\to\text{pr}^{*}(\ulcorner q_0\urcorner))\tag{1}$$

利用這個不動點, 我們可以證明 Gödel 第二不完備性定理的如下形式: 若 $\mathcal{N}$ 無矛盾, 則 $\mathcal{N}\not\vdash \text{con}_{\mathcal{N}}$.

反設 $\mathcal{N}\vdash \text{con}_{\mathcal{N}}$, 即 $\mathcal{N}\vdash\forall x_1\neg(\text{pr}(x_1)\wedge\text{pr}^{*}(x_1))$, 則有
$$\mathcal{N}\vdash\neg(\text{pr}(\ulcorner q_0\urcorner)\wedge\text{pr}^{*}(\ulcorner q_0\urcorner))\tag{2}$$
因此有
$$\mathcal{N}\cup\{\text{pr}(\ulcorner q_0\urcorner),q_0\}\vdash\neg\text{pr}^{*}(\ulcorner q_0\urcorner)\tag{3}$$
又由 $(1)$ 得
$$\mathcal{N}\cup\{\text{pr}(\ulcorner q_0\urcorner),q_0\}\vdash\text{pr}^{*}(\ulcorner q_0\urcorner)\tag{4}$$
結合 $(3)$, $(4)$ 用歸謬律可得
$$\mathcal{N}\vdash \text{pr}(\ulcorner q_0\urcorner))\to\neg q_0$$
令 $k$ 為公式 $\text{pr}(\ulcorner q_0\urcorner))\to\neg q_0$ 從 $\mathcal{N}$ 的一個證明的 Gödel 數. 則 $(\text{g}(q_0),k)\in\text{PRF}^{*}$, 所以有
$$\mathcal{N}\vdash \exists x_2\thinspace \text{prf}^{*}(\ulcorner q_0\urcorner,x_2)$$
即 $\mathcal{N}\vdash \text{pr}^{*}(\ulcorner q_0\urcorner))$.
由此可知, $\mathcal{N}\vdash \text{pr}(\ulcorner q_0\urcorner)\to\text{pr}^{*}(\ulcorner q_0\urcorner)$. 再結合 $(3)$ 即得 $\mathcal{N}\vdash q_0$, 進而由第一可推性條件得 $\mathcal{N}\vdash \text{pr}(\ulcorner q_0\urcorner))$.

最後, 結合兩式便有 $\mathcal{N}\vdash\text{pr}(\ulcorner q_0\urcorner)\wedge\text{pr}^{*}(\ulcorner q_0\urcorner)$, 與 $(2)$ 產生矛盾. 若 $\mathcal{N}$ 無矛盾, 則 $\mathcal{N}\not\vdash \text{con}_{\mathcal{N}}$. 這就證明了第二不完備性定理. $\square$

進而, 如果假定第二和第三可推性條件 (參見上文) 也成立, 那麼可以證明
$$\mathcal{N}\vdash\neg(\text{pr}(\ulcorner q_0\urcorner)\wedge\text{pr}^{*}(\ulcorner q_0\urcorner))\leftrightarrow\neg\text{pr}(\ulcorner \overline{0}\not\approx\overline{0}\urcorner)$$
後兩條可推性條件使得從 $\bot$ (矛盾) 推出公式 $\overline{0}\not\approx\overline{0}$ 的證明可在系統中再次形式化.

這給出了 Gödel 第二不完備性定理的一種通常的形式
$$\mathcal{N}\not\vdash \neg\text{pr}(\ulcorner \overline{0}\not\approx\overline{0}\urcorner)$$

直觀理解

對第二不完備性定理, 還有另一種 (不嚴格的) 直觀理解: 從 Gödel 句子 $p$ 出發, $p$ 等價於 “$p$ 不可證”, 所以如果 $\mathcal{N}$ 的無矛盾性在系統內可證, 那麼就能在系統內證明 “$p$ 不可證”, 也就證明了與之等價的 $p$. 這與 $p$ 的不可判定性矛盾. Hilbert 和 Bernays 最早完成了這種證明思路的嚴格化.

$K_N$ 的不可判定性

作為 Gödel-Rosser 定理的推論, 已經證明 $K_N$ 在 $\mathbb{N}$ 中恆真公式的 Gödel 數構成的集 $\text{TR}$ 是非遞歸的, 按 Church 論題, 不存在算法可以確定任給公式是否在 $\mathbb{N}$ 中恆真. 這一事實稱為 $K_N$ 的語義不可判定性, 而下面討論的是 $K_N$ 的語法不可判定性.

把從 $\mathcal{N}$ 可證的公式 Gödel 數全體構成的集記作 $\text{TH}$:
$$\text{TH}=\left\{\text{g}(p):\mathcal{N}\vdash p\right\}$$
由謂詞演算的可靠性定理知 $\text{TH}\subseteq\text{TR}$.

$K_N$ 的語法不可判定性是指: 若 $\mathcal{N}$ 無矛盾, 則 $\text{TH}$ 是非遞歸集.

反設 $\text{TH}$ 是遞歸的, 並設它用公式 $p(x_1)$ 可表示. 作一元遞歸函數 $f$:
$$f(n)=\text{Sub}(2^{15+2},\text{Num}(n),n)$$
$f(n)$ 的意思是用 $\overline{n}$ 去替換 Gödel 數為 $n$ 的公式中所有自由出現的 $x_1$ 所得結果的 Gödel 數. 設 $f$ 用公式 $s(x_1,y)$ 可表示.

記
$$
\begin{align*}
&r(x_1) = \forall x_2(s(x_1,x_2)\to\neg p(x_2)), \\
&m = \text{g}(r(x_1)), \\
&k = \text{g}(r(\overline{m})).
\end{align*}
$$
按 $f$ 的定義, $f(m)=k$. 由此可得:
$$
\begin{align*}
&\mathcal{N}\vdash s(\overline{m},\overline{k}), \tag{1} \\
&\mathcal{N}\vdash s(\overline{m},x_2)\to x_2\approx\overline{k}, \tag{2} \\
&r(\overline{m})=\forall x_2(s(\overline{m},x_2)\to\neg p(x_2)). \tag{3}
\end{align*}
$$

假設 $\mathcal{N}\vdash r(\overline{m})$, 即 $k\in\text{TH}$, 則 $\mathcal{N}\vdash p(\overline{k})$. 結合 $(3)$ 可得
$$\mathcal{N}\vdash s(\overline{m},\overline{k})\to\neg p(\overline{k})$$
再由 $(1)$ 又得 $\mathcal{N}\vdash\neg p(\overline{k})$, 於是產生矛盾.

假設 $r(\overline{m})$ 從 $\mathcal{N}$ 中不可證, 即 $k\not\in\text{TH}$, 則 $\mathcal{N}\vdash\neg p(\overline{k})$, 於是有
$$\mathcal{N}\vdash \overline{k}\approx x_2\to\neg p(x_2)$$
結合 $(2)$ 得到
$$\mathcal{N}\vdash s(\overline{m},x_2)\to\neg p(x_2)$$
使用 $\text{Gen}$ 規則即得 $\mathcal{N}\vdash r(\overline{m})$, 與假設不可證相矛盾. $\square$

綜上所述, $\text{TH}$ 是非遞歸集. 從而沒有算法能用來確定任給公式是否從 $\mathcal{N}$ 可證. 綜合語義和語法兩方面便知, 沒有算法可以用來確定任給公式是不是 Peano 形式算術的定理.

Hilbert 第十問題

能否設計出一個通用算法, 在有限步內確定一個任給的多元整係數方程 (丢番圖方程) 是否有整數解? 答案是否定的.

首先容易看出, 原問題等價於要求用算法判定任給丢番圖方程是否有正整數解. 因為要檢驗 $p(x_1,\cdots,x_n)=0$ 是否有整數解, 只需分別檢驗 $2^n$ 個方程
$$
\begin{align*}
&p(x_1,x_2\cdots,x_n) = 0 \\
&p(-x_1,x_2\cdots,x_n) = 0 \\
&p(x_1,-x_2\cdots,x_n) = 0 \\
&\cdots\cdots \\
&p(x_1,x_2\cdots,-x_n) = 0
\end{align*}
$$
是否有正整數解.

我們稱一個集合 $S$ 是丢番圖的, 當且僅當存在一個丢番圖方程 $p(x,y_1,\cdots,y_n)=0$ 使得 $x\in S$ $\Leftrightarrow$ $x$ 是方程 $p(x,y_1,\cdots,y_n)=0$ 的正整數解. 例如, 所有 $2$ 或 $3$ 的倍數構成的集 $A$ 是丢番圖集, 因為 $x\in A$ $\Leftrightarrow$ $x$ 是方程 $(x-2y_1)(x-3y_2)=0$ 的正整數解.

可以證明, 所有丢番圖集都是遞歸可枚舉的. 而 Matiyasevich 證明了其逆命題: 所有遞歸可枚舉集都是丢番圖集, 所以丢番圖集和遞歸可枚舉集是一回事. 我們已經證明了存在非遞歸的遞歸可枚舉集, 於是便可推知: 不存在 Hilbert 所要求的通用算法.

遞歸可枚舉集與算術集

可證公式集的遞歸可枚舉性

空集以及一元遞歸函數 (可以是部分遞歸函數) 的值域叫做遞歸可枚舉集. 非空集 $A$ 是遞歸可枚舉集, 意味著存在一元遞歸函數 $f$ 使
$$A=\left\{a:\exists n\in\mathbb{N}\enspace\text{s.t.}\enspace a=f(n)\right\}$$
根據 Church 論題, 存在算法能計算遞歸函數 $f$ 的函數值, 從而把 $A$ 的成員一個不漏 (但允許重複) 地列舉出來.

命題: 遞歸集一定是遞歸可枚舉集.
設非空集 $A$ 是遞歸集, 任取 $A$ 的元素 $a_0$. 取定 $a_0$ 後, 下式定義的遞歸函數 $f$ 的值域就是 $A$:
$$f(n)=nC_A(n)+a_0\thinspace\overline{\text{sg}}(C_A(n))$$
該函數相當於對自然數逐個檢驗的算法. 其中, 加上一項 $a_0\thinspace\overline{\text{sg}}(C_A(n))$ 是為了在輸入 $n_0\not\in A$ 時輸出 $a_0\in A$, 而非 $0$ (有可能 $0\not\in A$). $\square$

上述命題的逆命題不成立, 存在非遞歸的遞歸可枚舉集. 例如 $\text{TH}$ 是遞歸可枚舉集, 任取 $m\in\text{TH}$ (如取 $m$ 為某公理的 Gödel 數), 則如下定義的遞歸函數 $f$ 的值域給出 $\text{TH}$:
$$f(n)=(n)_{\text{lh}(n)\dot{-}1}\times C_{\text{PF}}(n)+m\thinspace\overline{\text{sg}}(C_{\text{PF}}(n))$$
直觀來看, 該算法的意思是: 逐一拿出從 $\mathcal{N}$ 的證明文章 (根據 $C_{\text{PF}}$ 的定義), 再取出文章的最後一個公式, 這樣就能枚舉出所有從 $\mathcal{N}$ 可證的公式.

進而, 若 $A$ 和 $A$ 的餘集 $\overline{A}=\mathbb{N}-A$ 都是遞歸可枚舉集, 則 $A$ 是遞歸集.
設非空集 $A$ 和非空集 $\overline{A}$ 分別是一元遞歸函數 $f$ 和 $h$ 的值域, 則 $A$ 的遞歸性由下式給出:
$$C_A(n)=\overline{\text{sg}}\left(n\ddot{-}f\left(\mu x\left[(f(x)\ddot{-}n)(h(x)\ddot{-}n)=0\right]\right)\right)$$
其中 $f$ 和 $h$ 的根存在性條件顯然滿足.

直觀來看, 如果 $A$ 是遞歸可枚舉集, 我們就可以逐一枚舉其元素. 對於任給的元素 $a$, 若 $a\in A$, 則必能在有限步內確定 $a\in A$, 但若 $a\not\in A$, 則無法用枚舉 $A$ 的元素的方法在有限步內確定 $a\not\in A$. 反過來, 如果 $\overline{A}$ 也是遞歸可枚舉集, 我們就可以通過枚舉 $\overline{A}$ 的元素, 在有限步內確定 $a\not\in A$. 這時 $A$ 和 $\overline{A}$ 就都是遞歸集.

遞歸可枚舉集的算術可定義性

〔註: 另參見筆記第二篇可定義性. 〕

$k$ 元函數 $f$ 是算術可定義函數, 指存在 $K_N$ 的含 $k+1$ 個自由變元的公式 $p(x_1\cdots,x_k,y)$, 對任意 $n_1,\cdots,n_k,m\in\mathbb{N}$, 滿足
$$f(n_1,\cdots,n_k)=m\enspace\Leftrightarrow\enspace |p(\overline{n_1},\cdots,\overline{n_k},\overline{m})|_{\mathbb{N}}=1$$
此時說 $f$ 用公式 $p(x_1\cdots,x_k,y)$ 在 $K_N$ 中可定義.

類似的, $k$ 元關係 $R$ 是算術可定義關係 (簡稱算術關係), 指存在 $K_N$ 的含 $k$ 個自由變元的公式 $p(x_1\cdots,x_k)$, 對任意 $n_1,\cdots,n_k\in\mathbb{N}$, 滿足
$$(n_1,\cdots,n_k)\in R\enspace\Leftrightarrow\enspace |p(\overline{n_1},\cdots,\overline{n_k})|_{\mathbb{N}}=1$$
此時說 $R$ 用公式 $p(x_1\cdots,x_k)$ 在 $K_N$ 中可定義. 一元算術關係簡稱算術集.

可表示函數是算術可定義的, 且所用公式相同; 可表示關係也是用相同公式可定義的. 根據 $K_N$ 的可靠性, 這是容易驗證的. 進而, 遞歸函數必為算術可定義函數, 遞歸關係必為算術可定義關係, 特別地, 遞歸集必為算術集.

還可以進一步得到: 遞歸可枚舉集必為算術集. 設非空集 $A$ 是遞歸可枚舉集, 並設它是一元遞歸函數 $f$ 的值域, 再設 $f$ 用公式 $p(x_1,y)$ 可表示. 則集合 $A$ 用公式 $\exists x\thinspace p(x,\overline{n})$ 可定義, 即 $A$ 滿足
$$n\in A\enspace\Leftrightarrow\enspace |\exists x\thinspace p(x,\overline{n})|_{\mathbb{N}}=1$$
具體驗證過程略. $\square$

但算術集不一定是遞歸可枚舉集, 換句話說, 算術集的類比遞歸集的類要大.
已知 $\text{TH}$ 是遞歸可枚舉集, 而 $\overline{\text{TH}}$ 不是遞歸可枚舉集, 但 $\text{TH}$ 和 $\overline{\text{TH}}$ 都是算術集. 這是因為, 設 $\text{TH}$ 用公式 $p(x_1)$ 可定義, 則 $\overline{\text{TH}}$ 用公式 $\neg p(x_1)$ 可定義.

真公式集的非算術可定義性

下證明真公式 (Gödel 數的) 集 $\text{TR}$ 是非算術集, 因而有 $\text{TH}\not=\text{TR}$, 即從 $\mathcal{N}$ 可證的公式集是真公式集的真子集.

定理(Tarski): $\text{TR}$ 不是算術集.
反設 $\text{TR}$ 是算術集, 並設它用公式 $p(x_1)$ 可定義:
$$n\in\text{TR}\enspace\Leftrightarrow\enspace |p(\overline{n})|_{\mathbb{N}}=1$$
作一元遞歸函數 $f$:
$$f(n)=\text{Sub}(2^{15+2},\text{Num}(n),n)$$
若 $n=\text{g}(q(x_1))$, 則 $f(n)=\text{g}(q(\overline{n}))$.

設 $f$ 用公式 $s(x_1,y)$ 可表示. 記
$$
\begin{align*}
&r(x_1) = \forall y(s(x_1,y)\to\neg p(y)), \\
&m = \text{g}(r(x_1)), \\
&k = \text{g}(r(\overline{m})).
\end{align*}
$$
按 $f$ 的定義, $f(m)=k$. 由此可得:
$$
\begin{align*}
&\mathcal{N}\vdash s(\overline{m},\overline{k}), \\
&\mathcal{N}\vdash s(\overline{m},t)\to t\approx\overline{k}.
\end{align*}
$$
這裡的定義方式與證明 $\text{TH}$ 的非遞歸性時幾乎相同, 但公式 $r(\overline{m})$ 的語義內容發生變化, $r(\overline{m})$ 斷言自身不真, 它表達的正是說謊者悖論.
考察 $r(\overline{m})$ 的真假, 立即能導出矛盾. 而矛盾的根源即是最初假定 $\text{TR}$ 是算術集的假設, 這就表明, $\text{TR}$ 不是算術集. $\square$

下圖展示了上文討論的幾類集合之間的關係:

Turing 機

Turing 機的定義

Turing 機是一種將人的計算行為抽象化的數理邏輯機, 也可以認為是一種可計算性的抽象模型. Turing 和 Gödel, Church 等人差不多同時給出了判定問題的否定答案, 但 Turing 的模型更接近實際計算的物理過程, 比形式系統更能代表機械裝置, 所以在不可判定問題上更有說服力.

直觀上, 一臺 Turing 機包含以下要素:

  1. 一個兩個方向都可無限延長的紙帶 (Tape), 被分成一個個小方格. 格子或者是空白的, 用 $0$ 表示, 或者寫上一個字符, 字符來自於一個事先給定的有限字母表 $\Sigma=\left\{a_1,\cdots,a_n,0\right\}$. 任何時刻紙帶上只有有限個非空格.
  2. 一個讀寫頭 (Head), 每次可掃描紙帶上的一個格子. 它可以識別格子是空白的還是有字符的, 可以在空白格子上寫入字符, 也可以把已有字符抹去, 使格子再變成空白的. 讀寫頭還可以左右移動, 每次移動一格.
  3. 一個有窮的內部狀態集 $Q=\left\{q_1,\cdots,q_n\right\}$, 在任一給定時刻, Turing 機都處在其中某個狀態 $q_i$.

設 $\Sigma$ 是一個有限字母表, 其中有 $0$, 還至少有一個非 $0$ 字母; $Q$ 是一個有限內部狀態集, 其中至少含有一個內部狀態 $q_0$.
帶有有限字母表 $\Sigma$ 和有限狀態集 $Q$ 的 Turing 機 $T$, 是指偏映射
$$T:Q\times \Sigma\to(\Sigma\cup\left\{L,R\right\})\times Q$$
其中 $L$, $R$ 分別表示左和右. $T$ 無定義時表示停機.

$Q$ 和 $\Sigma$ 都是有限集, 故 $T$ 的定義域是有限集. 定義一個 Turing 機, 只要給出它包含的全部四元組即可. 把四元組的集合稱為指令集 $\delta$, 其中每個指令是具有如下形式的四元組:

  1. $qaa’q’$, 其中 $q,q’\in Q$, $a,a’\in \Sigma$;
  2. $qaLq’$, 其中 $q,q’\in Q$, $a\in \Sigma$;
  3. $qaRq’$, 其中 $q,q’\in Q$, $a\in \Sigma$.

指令 $qaa’q’$ 解讀為: 當前狀態為 $q$ 且讀寫頭在格子裡讀到的字符是 $a$, 就把格子裡的 $a$ 改為 $a’$, 並把狀態改為 $q’$; 另外兩類指令的解讀類似, $L$ 和 $R$ 分別表示向左和向右移動一格. 一個四元組(指令)就對應著 “一步計算”.

藉助 Turing 機, 便可提出 Turing 可計算函數的概念.

採用如下方式, 每個 Turing 機都可用來定義一個一元部分函數 $\varphi$.
設 $T$ 的字母表除 $0$ 外還有 $1$, 如果以
$$\cdots010\enspace\overbrace{11\cdots1}^{n}\enspace0\cdots$$
的紙帶輸入 $T$ (簡稱 “以 $n$ 輸入 $T$” ) 經運算後能停機, 則令 $\varphi(n)=$ 輸出紙帶上非空格總數; 若不停機, 則 $\varphi(n)$ 無定義. 輸入紙帶前加上 “$\cdots010$” 是為了使自然數 $0$ 作為自變量的值能夠輸入.

把紙帶換為
$$\cdots010\enspace\overbrace{1\cdots1}^{m}\enspace0\enspace\overbrace{1\cdots1}^{n}\enspace0\cdots$$
即可定義二元部分函數 $\psi$. 進而, 可以利用 Turing 機來定義 $k$ 元部分函數 $f:\mathbb{N}^k\to\mathbb{N}$.

一個數論函數, 如果存在某個 Turing 機可用來定義它並計算它的函數值, 就叫做 Turing 可計算函數.

Turing 論題: 算法可計算函數 = Turing 可計算函數.
另外, 可以證明: Turing 可計算函數 = 遞歸函數.

停機問題

假定所有 Turing 機的字母表都取自一張通用字母表
$$\Sigma^{*}=\left\{A_0,A_1,A_2,\cdots\right\}$$
內部狀態符號都取自通用的狀態符號集
$$Q^{*}=\left\{q_0,q_1,q_2,\cdots\right\}$$
其中 $A_0$ 對應於空白, $q_0$ 對應於初始狀態. 如果兩個 Turing 機的差別僅在於它們使用的字母符號和狀態符號不一樣, 那麼我們把它們視為同一個 Turing 機, 因為它們進行本質相同的計算.

下面給每個 Turing 機指定碼數.

  1. 定義單個符號的碼數:
    $$
    \begin{array}{c|cc} a & L & R & A_i & q_i \\
    \hline \text{g}(a) & 1 & 3 & 4i+5 & 4i+7 \\
    \end{array}
    $$
  2. 定義四元組的編碼:
    $$\text{g}(abcd)=2^{\text{g}(a)}\thinspace3^{\text{g}(b)}\thinspace5^{\text{g}(c)}\thinspace7^{\text{g}(d)}$$
  3. 定義 Turing 機 $T=\left\{\sigma_0,\cdots,\sigma_n\right\}$ ($\sigma_i$ 為四元組) 的碼數為:
    $$\text{g}(T)=2^{\text{g}(\sigma_0)}\thinspace3^{\text{g}(\sigma_1)}\cdots\thinspace p_n^{\text{g}(\sigma_n)}$$
    其中四元組 $\sigma_0,\cdots,\sigma_n$ 按字典序排列.

這樣就給每一個 Turing 機指定了唯一的碼數. 按碼數大小, 我們把所有 Turing 機枚舉如下:
$$T_0,T_1,T_2,\cdots,T_n,\cdots$$

定義一元全函數 $f^{*}$ 如下:

  1. $f^{*}(n)=0$ $\Leftrightarrow$ $T_n$ 輸入 $n$ 後會停機;
  2. $f^{*}(n)=1$ $\Leftrightarrow$ $T_n$ 輸入 $n$ 後不停機.

假設存在某個 Turing 機 $T$ 能計算函數 $f^{*}$. 由於 $f^{*}$ 是全函數, $T$ 對任何輸入都停機. 利用 $T$ 構造一個新的 Turing 機 $T’$, 它包含 $T$ 的全部四元組, 並增加兩個新的狀態 $q_{\alpha}$, $q_{\beta}$ 和一個新的字母 $A$, 然後增加四元組
$$q_{\alpha}0Aq_{\beta},\enspace q_{\beta}0Aq_{\alpha},\enspace q_{\alpha}ARq_{\alpha},\enspace q_{\beta}ALq_{\beta}$$
此外, 對 $T$ 原先沒有定義的每個 $q_i S$, 增加四元組 $q_i SRq_{\alpha}$. 這樣做的目的是使 $T$ 在輸出 $0$ 後轉接到循環狀態, 從而無法停機.

由 $T’$ 的構造可知, $T$ 輸入 $n$ 後輸出 $1$ $\Leftrightarrow$ $T’$ 輸入 $n$ 後會停機.
$T’$ 必出現在 $T_0,T_1,T_2,\cdots$, 設 $T’=T_k$. 向 $T_k$ (即 $T’$) 輸入 $k$, 立即就會出現矛盾. 因此, 函數 $f^{*}$ 不是 Turing 可計算函數. $\square$

一個推論是: 停機問題是不可判定的. 即 “Turing 機 $T_m$ 在輸入 $n$ 後是否會停機” 這一問題類是不能用算法在有限步內判定的. 因為如果存在這樣的算法, 那麼 $f^{*}$ 也就有了計算其值的算法, 從而成了遞歸函數.