數理邏輯 (4) Gödel 不完備性定理

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

Gödel 不完備性定理

不完備性定理

Gödel 第一不完備性定理

用 $\mathsf{PA}$ 來表示 Peano 算術理論, 其公理集為一階邏輯公理集和算術公理集 $\mathcal{N}$. 由上一篇的分析, $\mathsf{PA}$ 是一個遞歸可公理化的理論.

---

根據上一篇的分析, 我們知道遞歸函數 $\text{Num}$ 和 $\text{Sub}$ 分別滿足:

$$\begin{align*} &\text{Num}(n) = \text{g}(\overline{n}) \\ &\text{Sub}(\text{g}(x),\text{g}(t),\text{g}(\varphi(x))) = \text{g}(\varphi(t)) \end{align*}$$

用 $\text{Num}$ 和 $\text{Sub}$ 定義一個新的二元遞歸函數 $\text{Su}$:

$$\text{Su}(n,m)=\text{Sub}\left(\text{g}(x),\text{Num}(n),m\right)$$

若 $m$ 是公式 $\varphi(x)$ 的 Gödel 數, 則 $\text{Su}(n,m)$ 是 $\varphi(\overline{n})$ 的 Gödel 數, 即

$$\text{Su}(n,\text{g}(\varphi(x)))=\text{g}(\varphi(\overline{n}))$$

設遞歸函數 $\text{Su}$ 用公式 $\text{su}(x_1,x_2,y)$ 可表示.

下面用 $\ulcorner\psi\urcorner$ 來表示 $\overline{\text{g}(\psi)}$, 即公式 $\psi$ 的 Gödel 數在形式算術 $K_N$ 中對應的數字 (作為形式系統中的一個閉項).

不動點引理: 對任一以 $x$ 為僅有自由變元的公式 $\varphi(x)$, 必存在閉式 $\sigma$ 滿足: $$\vdash_{\mathsf{PA}}\sigma\leftrightarrow\varphi(\ulcorner\sigma\urcorner)$$ 我們把具有這種性質的 $\sigma$ 叫做公式 $\varphi(x)$ 的不動點.

證明: 考慮公式 $\tau(x_1):=\exists y\left(\varphi(y)\wedge\text{su}(x_1,x_1,y)\right)$, 令 $m = \text{g}(\tau(x_1))$, 再令閉式 $\sigma$ 為:

$$\sigma:=\tau(\overline{m})=\exists y\left(\varphi(y)\wedge\text{su}(\overline{m},\overline{m},y)\right)$$

驗證如下:

$$\begin{aligned} \sigma & \Longleftrightarrow \exists y\left(\varphi(y)\wedge y\approx\tau(\overline{m})\right) \\ & \Longleftrightarrow \exists y\left(\varphi(y)\wedge y\approx \ulcorner\sigma\urcorner\right) \\ & \Longleftrightarrow\varphi(\ulcorner\sigma\urcorner) \end{aligned}$$

所以 $\sigma$ 是 $\varphi(x)$ 的不動點. $\square$

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

• 對所有 $n\in\mathbb{N}$, $\Gamma\vdash\varphi(\overline{n})$,
• $\Gamma\vdash\neg\forall x\varphi(x)$.

如果 $\Gamma$ 是 $\omega$-一致的, 那麼它也是一致的. 如果 $\Gamma$ 是 $\omega$-不一致的, 那麼 $\Gamma$ 顯然不能被自然數的標準模型滿足, 即 $\mathfrak{N}\nvDash\Gamma$. 我們在 $K_N$ 中添加新常元 $c$, 則公式集 $\mathsf{PA}\cup\lbrace c\not\approx\overline{n}:n\in\mathbb{N}\rbrace$ 是一致的, 但不是 $\omega$-一致的, 緊緻性定理表明該公式集被自然數的一個非標準模型滿足.

---

上一篇定義了遞歸關係 $\text{PRF}$: $(n,m)\in\text{PRF}$ $\Longleftrightarrow$ $n$ 編碼了以 $m$ 為編碼的公式在 $\mathsf{PA}$ 中的一個證明. 假設關係 $\text{PRF}$ 用公式 $\text{Prf}\left(y,x\right)$ 可表示, 並令

$$\text{Prov}(x):=\exists y\text{Prf}\left(y,x\right)$$

則 $\neg\text{Prov}(x)$ 是只含一個自由變元的公式, 根據不動點引理, 它存在不動點 $\sigma$:

$$\vdash_{\mathsf{PA}}\sigma\leftrightarrow\neg\text{Prov}\left(\ulcorner\sigma\urcorner\right)\tag{1}$$

引理 (第一可推性條件): 對任一公式 $\varphi$, $$\vdash_{\mathsf{PA}}\varphi\enspace\Longrightarrow\enspace\vdash_{\mathsf{PA}}\text{Prov}\left(\ulcorner\varphi\urcorner\right)$$

證明: 記 $m=\text{g}(\varphi)$, 則 $\overline{m}=\ulcorner\varphi\urcorner$. 設 $n$ 是 $\varphi$ 的一個證明的 Gödel 數, 則 $(n,m)\in\text{PRF}$, 從而 $\vdash_{\mathsf{PA}}\text{Prf}\left(\overline{n},\overline{m}\right)$. 於是 $\vdash_{\mathsf{PA}}\exists y\text{Prf}\left(y,\overline{m}\right)$, 即 $\vdash_{\mathsf{PA}}\text{Prov}\left(\ulcorner\varphi\urcorner\right)$. $\square$

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

• 若 $\mathsf{PA}$ 是一致的, 則 $\nvdash_{\mathsf{PA}}\sigma$,
• 若 $\mathsf{PA}$ 是 $\omega$-一致的, 則 $\nvdash_{\mathsf{PA}}\neg\sigma$.

證明: 假設 $\vdash_{\mathsf{PA}}\sigma$, 由第一可推性條件即得 $\vdash_{\mathsf{PA}}\text{Prov}\left(\ulcorner\sigma\urcorner\right)$, 又由 $(1)$ 式知 $\vdash_{\mathsf{PA}}\neg\text{Prov}\left(\ulcorner\sigma\urcorner\right)$, 表明 $\mathsf{PA}$ 不一致. 假設 $\vdash_{\mathsf{PA}}\neg\sigma$ 且 $\mathsf{PA}$ 是一致的, 那麼對任意 $n\in\mathbb{N}$ 都有 $\vdash_{\mathsf{PA}}\neg\text{Prf}\left(\overline{n},\ulcorner\sigma\urcorner\right)$, 否則與 $\mathsf{PA}$ 的一致性矛盾, 但 $\vdash_{\mathsf{PA}}\exists y\left(y,\ulcorner\sigma\urcorner\right)$, 表明 $\mathsf{PA}$ 是 $\omega$-不一致的. $\square$

令 $\mathsf{PA}^{\ast}$ 為 $\mathsf{PA}$ 的一個遞歸可公理化的一致擴張, 上述定理對 $\mathsf{PA}^{\ast}$ 也成立.

Gödel-Rosser 定理

Rosser 於1936年改進了 Gödel 的結果, 把 $\omega$-一致的條件減弱為一致, “從而完全擺脫了對語義的依賴”.

定理 (Gödel-Rosser): 如果 $\mathsf{PA}$ 是一致的, 那麼 $\mathsf{PA}$ 不完備.

證明: 假設 $\mathsf{PA}$ 是一致的. 考慮公式 $$\text{prov}(x):=\exists y\left(\text{Prf}\left(y,x\right)\wedge(\forall z<y)\neg\text{Prf}\left(z,\dot{\neg} x\right)\right)$$ 其中 $\dot{\neg}$ 是原始遞歸函數 $\text{g}(\varphi)\mapsto\text{g}(\neg\varphi)$ 在形式算術中的表示.

顯然 $\vdash_{\mathsf{PA}}\tau$ $\Longrightarrow$ $\vdash_{\mathsf{PA}}\text{prov}\left(\ulcorner\tau\urcorner\right)$. 反過來, 假設 $\vdash_{\mathsf{PA}}\neg\tau$, 那麼對某個 $n\in\mathbb{N}$ 有 $\vdash_{\mathsf{PA}}\text{Prf}\left(\overline{n},\ulcorner\neg\tau\urcorner\right)$, 一方面我們有 $\vdash_{\mathsf{PA}}(\forall y\le\overline{n})\neg\text{Prf}\left(y,\ulcorner\tau\urcorner\right)$, 另一方面 $\vdash_{\mathsf{PA}}(y>\overline{n})\to(\exists z<y)\text{Prf}\left(\overline{n},\ulcorner\neg\tau\urcorner\right)$ (取 $z=\overline{n}$ 即為一個見證), 從而必有 $\vdash_{\mathsf{PA}}\neg\text{prov}\left(\ulcorner\tau\urcorner\right)$.

設 $\sigma$ 為 $\neg\text{prov}(x)$ 的不動點, 即 $\vdash_{\mathsf{PA}}\sigma\leftrightarrow\neg\text{prov}\left(\ulcorner\sigma\urcorner\right)$. 由上面的分析知 $\vdash_{\mathsf{PA}}\sigma$ $\Longrightarrow$ $\vdash_{\mathsf{PA}}\text{prov}\left(\ulcorner\sigma\urcorner\right)$ 且 $\vdash_{\mathsf{PA}}\neg\sigma$ $\Longrightarrow$ $\vdash_{\mathsf{PA}}\neg\text{prov}\left(\ulcorner\sigma\urcorner\right)$, 兩邊都與 $\mathsf{PA}$ 的一致性矛盾. $\square$

直觀上, Gödel 語句 $\sigma_G$ 斷言其自身不可證, 而 Rosser 語句 $\sigma_R$ 斷言, 若其自身在 $\mathsf{PA}$ 中可證, 那麼其否定就也在 $\mathsf{PA}$ 中可證且證明更簡單 (對應 Gödel 數更小).

令 $\bot:=\overline{0}\not\approx\overline{0}$, $\top:=\neg\bot$. 下文將用 $\neg\text{Prov}(\bot)$ 來形式化 $\mathsf{PA}$ 的一致性, 記作 $\text{con}_{\mathsf{PA}}$, Gödel 第二不完備性定理表明 $\text{con}_{\mathsf{PA}}$ 是不可證的. 然而, 由於 $\vdash_{\mathsf{PA}}\top$, 我們有 $\vdash_{\mathsf{PA}}\neg\text{prov}(\bot)$. 事實上, $\neg\text{Prov}(\bot)$ 表示 $\forall y\left(\neg\text{Prf}\left(y,\ulcorner\bot\urcorner\right)\right)$, 而 $\neg\text{prov}(\bot)$ 表示 $\forall y\left(\neg\text{Prf}\left(y,\ulcorner\bot\urcorner\right)\vee(\exists z<y)\neg\text{Prf}\left(z,\ulcorner\top\urcorner\right)\right)$, 所以 $\vdash_{\mathsf{PA}}\neg\text{prov}(\bot)$ 比 $\vdash_{\mathsf{PA}}\neg\text{Prov}(\bot)$ 弱得多. 儘管如此, 在標準模型 $\mathfrak{N}$ 中兩者等價, 即 $\mathfrak{N}\vDash\text{Prov}(\tau)\leftrightarrow\text{prov}(\tau)$.

---

更一般地, 一個理論 $T$ 只要滿足如下條件就必是不完備的:

• $T$ 中包含足夠多的初等算術公理 (足以將語法算術化),
• $T$ 是遞歸可公理化的,
• $T$ 是一致的.

並非 $\mathsf{PA}$ 的任何一致擴張都不可能完備. 例如, 把所有標準模型 $\mathfrak{N}$ 滿足的 $K_N$ 公式構成的集記作 $\text{Tr}=\text{Th }\mathfrak{N}$, 則 $\text{Tr}$ 顯然是完備的. 由於 $\mathfrak{N}\vDash\mathsf{PA}$, 所以 $\text{Tr}$ 就是 $\mathsf{PA}$ 的一個完備一致擴張. 但是根據 Gödel-Rosser 定理, $\text{Tr}$ 不是遞歸可公理化的, 即 $\text{Tr}$ 中公式的 Gödel 數構成的集 $\text{TR}$ 不是遞歸集.

Gödel 第二不完備性定理

用 $\Box_T\varphi$ 表示語句 $\text{Prov}\left(\ulcorner\varphi\urcorner\right)$, 則 $\Box_T$ 可看作一個模態算子, 意為 (在 $T$ 中) “可證”. 用 $\text{con}_T$ 表示語句 $\neg\Box_T(\overline{0}\not\approx\overline{0})$, 字面意思即 “$T$ 是一致的”.

如下三條稱為 "可證性條件":

• $\text{(D1)}$ $T\vdash\varphi$ $\Longrightarrow$ $T\vdash\Box_T\varphi$,
• $\text{(D2)}$ $T\vdash\Box_T(\varphi\to\psi)\to\Box_T\varphi\to\Box_T\psi$,
• $\text{(D3)}$ $T\vdash\Box_T\varphi\to\Box_T\Box_T\varphi$.

$\text{(D1)}$ 和 $\text{(D2)}$ 分別相當於命題邏輯中的必然化規則 ($\text{RN}$) 和公理 $\text{K}$, $\text{(D3)}$ 相當於 $4$ 公理. 如果理論 $T$ 滿足 $\text{(D1)}$ 和 $\text{(D2)}$, 易知它也滿足:

• $\text{(D0)}$ 如果 $T,\sigma\vdash\tau$, 那麼 $T,\Box_T\sigma\vdash\Box_T\tau$.

上文已經證明了 $\mathsf{PA}$ 滿足條件 $\text{(D1)}$. 可以證明, 它也滿足另兩條可證性條件, 具體證明略過. 接下來侷限在 $\mathsf{PA}$ 中討論, 並省略 $\Box_{\mathsf{PA}}$ 的下標.

---

令 $\sigma$ 為公式 $\neg\text{Prov}(x)$ 的不動點, 則有

$$\vdash_{\mathsf{PA}}\sigma\leftrightarrow\neg\Box\sigma\tag{2}$$

引理: $\vdash_{\mathsf{PA}}\sigma\leftrightarrow\text{con}_{\mathsf{PA}}$, 即 $\text{con}_{\mathsf{PA}}$ 是等價意義下 $\neg\text{Prov}(x)$ 的唯一不動點.

證明: $\neg\Box\sigma$ 可寫成 $\Box\sigma\to\bot$, 由 $\sigma$ 的定義有 $\sigma\vdash_{\mathsf{PA}}\Box\sigma\to\bot$, 結合 $\text{(D0)}$ 和 $\text{(D2)}$ 可得 $\Box\sigma\vdash_{\mathsf{PA}}\Box\Box\sigma\to\Box\bot$. 根據 $\text{(D3)}$ 有 $\Box\sigma\vdash_{\mathsf{PA}}\Box\Box\sigma$, 所以 $\Box\sigma\vdash_{\mathsf{PA}}\Box\bot$. 另一方面顯然有 $\bot\vdash_{\mathsf{PA}}\sigma$, 從而 $\Box\bot\vdash_{\mathsf{PA}}\Box\sigma$. 因此, $\vdash_{\mathsf{PA}}\Box\sigma\leftrightarrow\Box\bot$, 代入 $(2)$ 式即得 $\vdash_{\mathsf{PA}}\sigma\leftrightarrow\neg\Box\bot$. $\blacksquare$

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

• $\vdash_{\mathsf{PA}}\text{con}_{\mathsf{PA}}\to\neg\Box\text{con}_{\mathsf{PA}}$,
• 如果 $\mathsf{PA}$ 是一致的, 則 $\nvdash_{\mathsf{PA}}\text{con}_{\mathsf{PA}}$.

證明: 在 $(2)$ 式中用 $\text{con}_{\mathsf{PA}}$ 代換 $\sigma$ 即得 $\vdash_{\mathsf{PA}}\text{con}_{\mathsf{PA}}\to\neg\Box\text{con}_{\mathsf{PA}}$; 假設 $\vdash_{\mathsf{PA}}\text{con}_{\mathsf{PA}}$, 根據 $\text{(D1)}$ 有 $\vdash_{\mathsf{PA}}\Box\text{con}_{\mathsf{PA}}$, 另一方面 $\vdash_{\mathsf{PA}}\neg\Box\text{con}_{\mathsf{PA}}$, 與 $\mathsf{PA}$ 的一致性矛盾. $\blacksquare$

1920年代, Hilbert 提出了著名的有窮主義綱領, 目的是要以無疑議的方式證明包含無窮的經典數學能夠幫助我們獲得關於物理現實中有限事物的知識, 從而在實質上消除爭議不斷的 "無窮" 概念. 為此, Hilbert 構建了只含原始遞歸函數的原始遞歸算術系統 ($\mathsf{PRA}$), 於是其目標就歸約為證明 Peano 算術 ($\mathsf{PA}$) 相對於 $\mathsf{PRA}$ 的保守性, 而保守性又可進一步歸約為從 $\mathsf{PRA}$ 中證明 $\mathsf{PA}$ 的無矛盾性 (把這裡的 $\mathsf{PA}$ 換成比方說 $\mathsf{ZFC}$, 就可以涵蓋更廣泛的數學領域, 而不僅僅是算術). 然而, Gödel 的第二不完備性定理否定了這個可能, 使得 Hilbert 的有窮主義綱領無法按其原意得到實現.

Löb 定理

已知 $\text{con}_{\mathsf{PA}}$ 是 $\neg\text{Prov}(x)$ 的不動點, 下面考慮 $\text{Prov}(x)\to\varphi$ 的不動點 $\sigma$. 我們有

$$\vdash_{\mathsf{PA}}\sigma\leftrightarrow(\Box\sigma\to\varphi)\tag{3}$$

Löb 定理:

• $\vdash_{\mathsf{PA}}\Box(\Box\varphi\to\varphi)\to\Box\varphi$,
• 如果 $\vdash_{\mathsf{PA}}\Box\varphi\to\varphi$, 則 $\vdash_{\mathsf{PA}}\varphi$.

證明: 由 $\sigma\vdash_{\mathsf{PA}}(\Box\sigma\to\varphi)$ 可得 $\Box\sigma\vdash_{\mathsf{PA}}(\Box\Box\sigma\to\Box\varphi)$, 根據 $\text{(D3)}$ 有 $\Box\sigma\vdash_{\mathsf{PA}}\Box\varphi$; 另一方面, 由 $\vdash_{\mathsf{PA}}\varphi\to(\Box\sigma\to\varphi)$ 和 $(3)$ 式可得 $\vdash_{\mathsf{PA}}\varphi\to\sigma$, 從而 $\Box\varphi\vdash_{\mathsf{PA}}\Box\sigma$. 因此, $\vdash_{\mathsf{PA}}\Box\sigma\leftrightarrow\Box\varphi$, 代入 $(3)$ 式可得 $\vdash_{\mathsf{PA}}\sigma\leftrightarrow(\Box\varphi\to\varphi)$, 進而 $\vdash_{\mathsf{PA}}\Box\sigma\leftrightarrow\Box(\Box\varphi\to\varphi)$, 再做一次代換即得到 $\vdash_{\mathsf{PA}}\Box(\Box\varphi\to\varphi)\to\Box\varphi$. $\blacksquare$

推論: $\top=\neg\bot$ 是等價意義下公式 $\text{Prov}(x)$ 的唯一不動點.

用 Löb 定理證明第二不完備性定理: 假設 $\mathsf{PA}$ 是一致的, 如果 $\vdash_{\mathsf{PA}}\text{con}_{\mathsf{PA}}$, 那麼 $\vdash_{\mathsf{PA}}\Box\bot\to\bot$, 由 Löb 定理, $\vdash_{\mathsf{PA}}\bot$, 與 $\mathsf{PA}$ 的一致性矛盾.

語法不可判定性

作為 Gödel-Rosser 定理的推論, 上文已經證明 $\text{Th }\mathfrak{N}$ 中公式的 Gödel 數構成的集 $\text{TR}$ 是非遞歸的, 我們稱 $\text{Th }\mathfrak{N}$ 是不可判定的, 或稱之為形式算術的語義不可判定性. 下面來看可證公式集的不可判定性, 即語法不可判定性.

把 $\mathsf{PA}$ 中全體可證公式的 Gödel 數構成的集記作 $\text{TH}$:

$$\text{TH}=\lbrace\text{g}(\varphi):\ \vdash_{\mathsf{PA}}\varphi\rbrace$$

由一階邏輯的可靠性定理知 $\text{TH}\subseteq\text{TR}$.

定理: 若 $\mathsf{PA}$ 是一致的, 則 $\text{TH}$ 不是遞歸集.

證明: 反設 $\text{TH}$ 是遞歸集, 並設它用公式 $\text{Th}(x)$ 可表示. 考慮 $\neg\text{Th}(x)$ 的不動點 $\sigma$, 我們有

$$\vdash_{\mathsf{PA}}\sigma\leftrightarrow\neg\text{Th}\left(\ulcorner\sigma\urcorner\right)$$

如果 $\ulcorner\sigma\urcorner\notin\text{TH}$, 由可表示性知 $\vdash_{\mathsf{PA}}\neg\text{Th}\left(\ulcorner\sigma\urcorner\right)$, 從而 $\vdash_{\mathsf{PA}}\sigma$, 所以 $\sigma\in\text{TH}$; 如果 $\ulcorner\sigma\urcorner\in\text{TH}$, 同樣由可表示性知 $\vdash_{\mathsf{PA}}\text{Th}\left(\ulcorner\sigma\urcorner\right)$, 從而 $\vdash_{\mathsf{PA}}\neg\sigma$, 所以 $\sigma\notin\text{TH}$. $\square$

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

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

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

$$\begin{align*} &p\left(x_1,x_2\cdots,x_n\right) = 0 \\ &p\left(-x_1,x_2\cdots,x_n\right) = 0 \\ &p\left(x_1,-x_2\cdots,x_n\right) = 0 \\ &\cdots \\ &p\left(x_1,x_2\cdots,-x_n\right) = 0 \end{align*}$$

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

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

遞歸可枚舉集與算術集

遞歸可枚舉集

空集以及一元遞歸函數 (可以是部分遞歸函數) 的值域叫做遞歸可枚舉集. 非空集 $A$ 是遞歸可枚舉集, 意味著存在一元遞歸函數 $f$ 使得

$$A=\lbrace a:\exists n\in\mathbb{N}\left(a=f(n)\right)\rbrace$$

根據 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))$$

其中, $C_A$ 是 $A$ 的特徵函數, 加上一項 $a_0\thinspace\overline{\text{sg}}(C_A(n))$ 是為了在輸入 $n_0\not\in A$ 時輸出 $a_0\in A$, 而非 $0$ (有可能 $0\not\in A$). $\square$

上述命題的逆命題不成立: 存在非遞歸的遞歸可枚舉集. 例如 $\mathsf{PA}$ 的可證公式集 $\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))$$ 該算法的意思是: 逐一取出 $\mathsf{PA}$ 中的證明 (有限公式序列), 並取出該公式序列的最後一個公式, 這樣就能枚舉出 $\mathsf{PA}$ 的全部可證公式.

---

命題: 若 $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$ 的根存在性條件顯然滿足. $\square$

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

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

$k$ 元函數 $f$ 是算術可定義函數, 指存在 $K_N$ 的含 $k+1$ 個自由變元的公式 $\varphi(x_1\cdots,x_k,y)$, 對任意 $n_1,\cdots,n_k,m\in\mathbb{N}$, 滿足 $$f(n_1,\cdots,n_k)=m\Longleftrightarrow\mathfrak{N}\vDash\varphi(\overline{n_1},\cdots,\overline{n_k},\overline{m})$$ 稱 $f$ 用公式 $\varphi(x_1\cdots,x_k,y)$ 可定義.

$k$ 元關係 $R$ 是算術可定義關係 (簡稱算術關係), 指存在 $K_N$ 的含 $k$ 個自由變元的公式 $\psi(x_1\cdots,x_k)$, 對任意 $n_1,\cdots,n_k\in\mathbb{N}$, 滿足 $$(n_1,\cdots,n_k)\in R\Longleftrightarrow\mathfrak{N}\vDash\psi(\overline{n_1},\cdots,\overline{n_k})$$ 稱 $R$ 用公式 $\psi(x_1\cdots,x_k)$ 可定義. 一元算術關係簡稱算術集.

---

可表示函數是算術可定義的, 且所用公式相同; 可表示關係也是用相同公式可定義的. 從而遞歸函數必為算術可定義函數, 遞歸關係必為算術可定義關係; 特別地, 遞歸集必為算術集.

還可以進一步得到: 遞歸可枚舉集必為算術集. 設非空集 $A$ 是遞歸可枚舉集, 並設它是一元遞歸函數 $f$ 的值域, 再設 $f$ 用公式 $\varphi(x,y)$ 可表示, 則集合 $A$ 用公式 $\exists x\varphi(x,\overline{n})$ 可定義, 即 $A$ 滿足

$$n\in A\Longleftrightarrow\mathfrak{N}\vDash\exists x\varphi(x,\overline{n})$$

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

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

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

定理 (Tarski): $\text{TR}$ 不是算術可定義集.

證明: 對任何一個公式 $\varphi(x)$, 考慮 $\neg\varphi(x)$ 的不動點 $\sigma$, 我們有 $$\vdash_{\mathsf{PA}}\sigma\leftrightarrow\neg\varphi\left(\ulcorner\sigma\urcorner\right)$$ 由可靠性定理得 $$\mathfrak{N}\vDash\sigma\leftrightarrow\neg\varphi\left(\ulcorner\sigma\urcorner\right)$$ 所以 $\mathfrak{N}\vDash\sigma$ $\Longleftrightarrow$ $\mathfrak{N}\nvDash\varphi\left(\ulcorner\sigma\urcorner\right)$, 這就排除了 $\varphi(x)$ 定義 $\text{TR}$ 的可能. $\square$

直觀上, 不動點 $\sigma$ 斷言其自身不真, 它表達的正是撒謊者悖論.

該定理又稱為 Tarski 的真之不可定義性定理.

---

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

Turing 機

定義

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

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

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

設 $\Sigma$ 是一個有限字母表, 其中有 $0$, 還有至少一個非 $0$ 字母; $Q$ 是一個有限內部狀態集, 其中至少含有一個內部狀態 $q_0$.

帶有有限字母表 $\Sigma$ 和有限狀態集 $Q$ 的 Turing 機 $T$, 是指偏映射 $$T:Q\times \Sigma\to\left(\Sigma\cup\lbrace L,R\rbrace\right)\times Q$$ 其中 $L$, $R$ 分別表示左和右. $T$ 無定義時表示停機.

$Q$ 和 $\Sigma$ 都是有限集, 故 $T$ 的定義域是有限集. 定義一個 Turing 機, 只要給出它包含的全部四元組即可.

把四元組的集合稱為指令集 $\delta$, 其中每個指令是具有如下形式的四元組:

• $qaa'q'$, 其中 $q,q'\in Q$, $a,a'\in \Sigma$,
• $qaLq'$, 其中 $q,q'\in Q$, $a\in \Sigma$,
• $qaRq'$, 其中 $q,q'\in Q$, $a\in \Sigma$.

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

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^{\ast}=\lbrace A_0,A_1,A_2,\cdots\rbrace$$

內部狀態符號都取自通用的狀態符號集

$$Q^{\ast}=\lbrace q_0,q_1,q_2,\cdots\rbrace$$

其中 $A_0$ 對應於空白, $q_0$ 對應於初始狀態. 如果兩個 Turing 機的差別僅在於它們使用的字母符號和狀態符號不一樣, 那麼我們把它們視為同一個 Turing 機, 因為它們進行本質相同的計算.

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

1. 定義單個符號的碼數:
$$\begin{array}{c|cccc} 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=\lbrace\sigma_0,\cdots,\sigma_n\rbrace$ ($\sigma_i$ 為四元組, 按字典序排列) 的碼數為:
$$\text{g}(T):=2^{\text{g}(\sigma_0)}\thinspace3^{\text{g}(\sigma_1)}\cdots\thinspace p_n^{\text{g}(\sigma_n)}$$

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

$$T_0,T_1,T_2,\cdots,T_n,\cdots$$

定理: 存在 Turing 機不能計算的函數.

證明: 定義一元全函數 $f^{\ast}$ 如下:

• $f^{\ast}(n)=0$ $\Longleftrightarrow$ $T_n$ 輸入 $n$ 後會停機,
• $f^{\ast}(n)=1$ $\Longleftrightarrow$ $T_n$ 輸入 $n$ 後不停機.

假設存在某個 Turing 機 $T$ 能計算函數 $f^{\ast}$, 由於 $f^{\ast}$ 是全函數, $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$ $\Longleftrightarrow$ $T'$ 輸入 $n$ 後會停機.

$T'$ 必出現在 $T_0,T_1,T_2,\cdots$ 中, 設 $T'=T_k$. 向 $T_k$ (即 $T'$) 輸入 $k$, 立即就會出現矛盾. 因此, 函數 $f^{\ast}$ 不是 Turing 可計算函數. $\square$

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