數理邏輯 (3) 形式算術與遞歸函數

上一篇: 一階邏輯

形式算術

Peano 形式算術

形式算術 $K_N$ 指一種特殊的帶等詞的謂詞演算, 它有一個個體常元 $c_1$, 三個函數詞: $f^1_1$, $f^2_1$, $f^2_2$ 和一個二元謂詞 $\approx$.

$K_N$ 有一個自然的模型: $\mathfrak{N}=\langle\mathbb{N},0,\mathsf{S},+,\times,=\rangle$. 在模型 $\mathfrak{N}$ 中, $c_1$ 解釋為 $0$; $f^1_1$, $f^2_1$, $f^2_2$ 分別解釋為一元後繼函數 $\mathsf{S}$, 二元和函數 $+$ 和二元乘積函數 $\times$; 等詞 $\approx$ 解釋為自然數的相等 ($=$).

下面把個體常元 $c_1$ 寫成 $\overline{0}$, $f^1_1(t)$, $f^2_1(t_1,t_2)$, $f^2_2(t_1,t_2)$ 分別寫成 $\mathsf{S}t$, $t_1+t_2$, $t_1\times t_2$. 在 $\mathfrak{N}$ 中常元 $\overline{0}$ 解釋為 $0$, 項 $\mathsf{S}\overline{0}$ 解釋為 $\mathsf{S}0=1$. 下面把閉項 $\mathsf{S}\overline{0},\mathsf{S}\mathsf{S}\overline{0},\cdots$ 分別寫作 $\overline{1},\overline{2},\cdots$, 這些形為 $\overline{n}$ 的閉項叫做 $K_N$ 的數字.

關於等詞 $\approx$ 有如下三條公理:

• $\text{(E1)}$ $t\approx t$,
• $\text{(E2)}$ $t_k\approx u\to f(t_1,\cdots,t_k,\cdots,t_n)\approx f(t_1,\cdots,u,\cdots,t_n)$,
• $\text{(E3)}$ $t_k\approx u\to (R(t_1,\cdots,t_k,\cdots,t_n)\to R(t_1,\cdots,u,\cdots,t_n))$.

$K_N$ 中所有等詞公理及如下形式的公式都叫做算術公理:

• $\text{(N1)}$ $\mathsf{S}t\not\approx\overline{0}$,
• $\text{(N2)}$ $\mathsf{S}t_1\approx\mathsf{S}t_2\to t_1\approx t_2$,
• $\text{(N3)}$ $t+\overline{0}\approx t$,
• $\text{(N4)}$ $t_1+\mathsf{S}t_2\approx\mathsf{S}(t_1+t_2)$,
• $\text{(N5)}$ $t\times\overline{0}\approx\overline{0}$,
• $\text{(N6)}$ $t_1\times\mathsf{S}t_2\approx t_1\times t_2+t_1$,
• $\text{(N7)}$ $\varphi(\overline{0})\to(\forall x(\varphi(x)\to\varphi(x'))\to\forall x\varphi(x))$, 其中 $\varphi(x)$ 是任意的公式.

算術公理的集記作 $\mathcal{N}$. 帶有算術公理集 $\mathcal{N}$ 的 $K_N$ 叫做 Peano 形式算術. 注意等詞公理集 $\mathcal{E}\subset\mathcal{N}$; $K_N$ 的公理除算術公理外還有謂詞演算公理 $\text{(K1)}$~$\text{(K5)}$.

若 $\mathcal{N}\vdash\varphi$, 則稱 $\varphi$ 為 Peano 形式算術的定理. 通常的關於自然數的定理可以批量翻譯成形式定理, 但其形式證明一般都很複雜.

"建立形式算術的主要目的之一, 是用以探討關於自然數的性質, 我們究竟能精確而機械地抓住些什麼."

可表示性

可表示函數

$k$ 元函數 $f:\mathbb{N}^k\to\mathbb{N}$ 在 $K_N$ 中可表示, 是指存在含 $k+1$ 個自由變元的公式 $\varphi(x_1,\cdots,x_k,y)$ 具有如下性質: 對任意 $n_1,\cdots,n_k,m\in\mathbb{N}$,

1. $f(n_1,\cdots,n_k)=m$ $\Longrightarrow$ $\mathcal{N}\vdash\varphi(\overline{n_1},\cdots,\overline{n_k},\overline{m})$,
2. $f(n_1,\cdots,n_k)\not=m$ $\Longrightarrow$ $\mathcal{N}\vdash\neg\varphi(\overline{n_1},\cdots,\overline{n_k},\overline{m})$,
3. $\mathcal{N}\vdash\varphi(\overline{n_1},\cdots,\overline{n_k},t)\to t\approx\overline{f(n_1,\cdots,n_k)}$, 其中 $t$ 對公式 $\varphi$ 中的 $y$ 自由.

$K_N$ 中的公式不一定能用來表示某個數論函數, 且同一公式不能用來表示兩個不同的數論函數. 由於所有數論函數構成的集是不可數的, 而 $K_N$ 中所有公式構成可數集, 所以並非每個數論函數都能用 $K_N$ 中公式表示.

---

定義 $k$ 元投影函數 $\pi^k_i$:

$$\pi^k_i(n_1,\cdots,n_k)=n_i,\enspace i=1,\cdots,k$$

函數 $+$, $\times$, $\pi^k_i$ 在 $K_N$ 中是可表示的:

• 二元和函數 $+$ 由公式 $x_1+x_2\approx y$ 表示;
• 二元乘積函數 $\times$ 由公式 $x_1\times x_2\approx y$ 表示;
• $\pi^k_i$ 由公式 $x_1\approx x_1\wedge\cdots\wedge x_k\approx x_k\wedge y\approx x_i$ 表示.

命題: 函數的複合保持可表示性. 即, 若 $j$ 元函數 $g$ 和 $j$ 個 $k$ 元函數 $h_1,\cdots,h_j$ 可表示, 那麼如下定義的 $k$ 元函數 $f$ 也是可表示的: $$f(n_1,\cdots,n_k)=g\left(h_1(n_1,\cdots,n_k),\cdots,h_j(n_1,\cdots,n_k)\right)$$

證明: 設 $g, h_1,\cdots,h_j$ 分別用公式

$$\psi(x_1,\cdots,x_j,y),\gamma_1(x_1,\cdots,x_k,y),\cdots,\gamma_j(x_1,\cdots,x_k,y)$$

可表示, 則 $f$ 可由如下公式表示:

$$\exists y_1\cdots\exists y_j\left(\gamma_1(x_1,\cdots,x_k,y_1)\wedge\cdots\wedge \gamma_j(x_1,\cdots,x_k,y_j)\wedge\psi(y_1,\cdots,y_j,y)\right)$$

其中 $y_1,\cdots,y_j$ 是不在 $\psi(x_1,\cdots,x_j,y)$, $\gamma_1(x_1,\cdots,x_k,y)$, $\cdots$, $\gamma_j(x_1,\cdots,x_k,y)$ 中出現的變元. $\square$

可表示關係

$k$ 元關係 $R$ 在 $K_N$ 中可表示, 是指存在含 $k$ 個自由變元的公式 $\varphi(x_1,\cdots,x_k)$ 具有如下性質: 對任意 $n_1,\cdots,n_k\in\mathbb{N}$,

1. $(n_1,\cdots,n_k)\in R$ $\Longrightarrow$ $\mathcal{N}\vdash\varphi(\overline{n_1},\cdots,\overline{n_k})$,
2. $(n_1,\cdots,n_k)\notin R$ $\Longrightarrow$ $\mathcal{N}\vdash\neg\varphi(\overline{n_1},\cdots,\overline{n_k})$.

是否每個 $K_N$ 的公式 $\varphi(x_1,\cdots,x_k)$ 都一定可以用來表示某個 $k$ 元關係?

如果存在公式 $\varphi(x_1,\cdots,x_k)$ 及 $n_1,\cdots,n_k\in\mathbb{N}$, 使得 $\mathcal{N}\nvdash\varphi(\overline{n_1},\cdots,\overline{n_k})$ 且 $\mathcal{N}\nvdash\neg\varphi(\overline{n_1},\cdots,\overline{n_k})$, 則稱閉式 $\varphi(\overline{n_1},\cdots,\overline{n_k})$ 是一個從 $\mathcal{N}$ 不可判定的公式, 並且稱 $\mathcal{N}$ 是不完備的. 這時, 公式 $\varphi(x_1,\cdots,x_k)$ 不能用來表示任何一個關係; 反之, 如果 $\mathcal{N}$ 是完備的, 那麼任何公式 $\varphi(x_1,\cdots,x_k)$ 都一定表示某個 $k$ 元關係.

---

$k$ 元關係 $R$ 的特徵函數 $C_R:\mathbb{N}^k\to\left\{0,1\right\}$ 定義為: $$C_R(n_1,\cdots,n_k)=\begin{cases} 1,&(n_1,\cdots,n_k)\in R\\ 0,&(n_1,\cdots,n_k)\notin R \end{cases}$$

若關係 $R$ 用公式 $\varphi(x_1,\cdots,x_k)$ 可表示, 則函數 $C_R$ 可用如下公式表示: $$(\varphi(x_1,\cdots,x_k)\wedge y\approx 1)\vee(\neg\varphi(x_1,\cdots,x_k)\wedge y\approx 0)$$ 若 $C_R$ 用公式 $\psi(x_1,\cdots,x_k,y)$ 可表示, 則 $R$ 用如下公式可表示: $$\psi(x_1,\cdots,x_k,\overline{1})$$ 因此, 關係 $R$ 可表示當且僅當 $R$ 的特徵函數 $C_R$ 可表示.

例如, 二元關係 $\leq$ 用公式 $\exists z(z+x_1\approx x_2)$ 可表示, 從而它的特徵函數 $C_{\leq}$ 也是可表示的.

最小數算子

設 $k+1$ 元函數 $g$ 滿足 “根存在條件”: 對任意 $n_1,\cdots,n_k$ 都存在自然數 $x$ 使 $g(n_1,\cdots,n_k,x)=0$. 定義 $k$ 元函數 $f$ 如下:

$$f(n_1,\cdots,n_k)=\min\left\{x:g(n_1,\cdots,n_k,x)=0\right\}$$

即 $f(n_1,\cdots,n_k)$ 是使 $g(n_1,\cdots,n_k,x)=0$ 的 $x$ 的最小值. 稱 $f$ 是由 $g$ 使用最小數算子或 $\mu$ 算子得來的, 記作

$$f(n_1,\cdots,n_k)=\mu x\left[g(n_1,\cdots,n_k,x)=0\right]$$

$\mu$ 算子保持可表示性: 若 $k+1$ 元函數 $g$ 在 $K_N$ 中可用 $\psi(x_1,\cdots,x_{k+1},y)$ 表示, 則對 $g$ 使用 $\mu$ 算子得到的 $k$ 元函數 $f$ 在 $K_N$ 中用如下公式表示: $$\psi(x_1,\cdots,x_k,y,\overline{0})\wedge\forall x (\psi(x_1,\cdots,x_k,x,\overline{0})\to y\leq x)$$ 其中 $x$ 取不在 $\psi(x_1,\cdots,x_k,y,\overline{0})$ 中出現的變元.

遞歸函數

原始遞歸函數

如下三類函數稱為初始函數:

• 一元零函數 $\mathsf{Z}$, $\mathsf{Z}(n)=0$,
• 一元後繼函數 $\mathsf{S}$, $\mathsf{S}(n)=n+1$,
• $k$ 元投影函數 $\pi^k_i$, $\pi^k_i(n_1,\cdots,n_k)=n_i$, $i=1,\cdots,k$.

設 $g$ 和 $h$ 分別是 $k$ 元函數和 $k+2$ 元函數, 稱 $k+1$ 元函數 $f$ 是由 $g$ 和 $h$ 經原始遞歸得到的, 如果

$$\begin{align*} f(n_1,\cdots,n_k,0) &= g(n_1,\cdots,n_k), \\ f(n_1,\cdots,n_k,y+1) &= h(n_1,\cdots,n_k,y,f(n_1,\cdots,n_k,y)) \end{align*}$$

特別地, 當 $n=0$ 時, 規定 $0$ 元函數 $g$ 為一個常數 $c$. 此時,

$$\begin{align*} f(0) &= c, \\ f(y+1) &= h(y,f(y)) \end{align*}$$

全體原始遞歸函數的集合 $\mathcal{C}$ 是最小的滿足如下條件的 $\mathbb{N}$ 上函數的集合:

1. 初始函數屬於 $\mathcal{C}$,
2. $\mathcal{C}$ 對函數複合封閉,
3. $\mathcal{C}$ 對原始遞歸封閉.

$\mathcal{C}$ 中的函數稱為原始遞歸函數.

---

下面是一些常用的原始遞歸函數:

• $k$ 元常值函數 $\mathsf{C}_m(n_1,\cdots,n_k)=m$:

$$\begin{align*} &\mathsf{C}_0(n_1,\cdots,n_k) = \mathsf{Z}(\pi^k_1(n_1,\cdots,n_k)), \\ &\mathsf{C}_{m+1}(n_1,\cdots,n_k) = \mathsf{S}(\mathsf{C}_m(n_1,\cdots,n_k)). \end{align*}$$

• 二元和函數 $+$:

$$\begin{align*} &n+0 = \pi^1_1(n), \\ &n+(m+1) = \mathsf{S}(\pi^3_3(n,m,n+m)). \end{align*}$$

• 二元乘積函數 $\times$:

$$\begin{align*} &n\times 0 = \mathsf{Z}(n), \\ &n\times (m+1) = \pi^3_3(n,m,n\times m)+\pi^3_1(n,m,n\times m). \end{align*}$$

• 前鄰函數 $\text{pred}$, 若 $n=0$ 則 $\text{pred}(n)=0$, 否則 $\text{pred}(n)=n-1$:

$$\begin{align*} &\text{pred}(n) = 0, \\ &\text{pred}(n+1) = \pi^2_1(n,\text{pred}(n)). \end{align*}$$

• 截差函數 $\dot{-}$, 若 $n\ge m$, 則 $n\dot{-}m=n-m$, 否則 $n\dot{-}m=0$:

$$\begin{align*} &n\dot{-}\ 0 = \pi^1_1(n), \\ &n\dot{-}(m+1) = \text{pred}(\pi^3_3(n,m,n\dot{-}m)). \end{align*}$$

• 非零檢測函數 $\text{sg}$, 若 $n=0$ 則 $\text{sg}(n)=0$, 否則 $\text{sg}(n)=1$:

$$\begin{align*} &\text{sg}(0) = 0, \\ &\text{sg}(n+1) = \mathsf{C}_1(n,\text{sg}(n)). \end{align*}$$

• 零檢測函數 $\overline{\text{sg}}(n)=1\dot{-}\text{sg}(n)$.

• 絕對差 $\ddot{-}$, $n\ddot{-}m=|n-m|=(n\dot{-}m)+(m\dot{-}n)$.

• $k$ 元最值函數 $\min$, $\max$:

$$\begin{align*} &k=2,\enspace\min(n_1,n_2) = n_1\dot{-}(n_1\dot{-}n_2), \\ &k>2,\enspace\min(n_1,\cdots,n_n) = \min(\min(n_1,\cdots,n_{k-1}),n_k). \end{align*}$$

• 指數函數 $n^m$, 其中 $n\not=0$:

$$\begin{align*} &n^0 = \text{sg}(n), \\ &n^{m+1} = n^m\times n \end{align*}$$

• 餘數函數 $\text{rem}$, 若 $n>0$, $\text{rem}(n,m)$ 是用 $n$ 除 $m$ 所得餘數; 若 $n=0$ 則 $\text{rem}(n,m)=0$:

$$\begin{align*} &\text{rem}(n,0) = 0, \\ &\text{rem}(n,m+1) = (\text{rem}(n,m)+1)\times\text{sg}(n\dot{-}(\text{rem}(n,m)+1)) \end{align*}$$

• 若 $f(\alpha,m)$ 是原始遞歸的, 則有界和 $\sum_{m\le l}f(\alpha,m)$ 和有界乘積 $\prod_{m\le l}f(\alpha,m)$ 也是原始遞歸的, 其中 $\alpha$ 是 $n_1,\cdots,n_k$ 的縮寫.

---

命題: 由 $k$ 元原始遞歸函數 $f$ 用下式定義的 $l$ 元函數 $g$ 也是原始遞歸的: $$g(n_1,\cdots,n_l)=f(n_{m_1},\cdots,n_{m_k})$$ 其中每個 $1\le m_i\le l$.

該命題可由於 “增元” 或 “減元”.

---

原始遞歸函數顯然是可計算的, 但並非所有直觀上可計算的函數都是原始遞歸函數. 我們可以能行地列出全部遞歸函數: $g_0, g_1, \cdots$ 並使用對角線方法: 定義函數 $F:\mathbb{N}\to\mathbb{N}$ 為 $F(n)=g_n(n)+1$. $F$ 顯然不同於任何一個已列出的原始遞歸函數. 但直觀來看, 這個函數明顯是可計算的.

此外還有如下更具體的例子:

Ackermann 函數 $A(n,m)$ 定義為: $$\begin{align*} &A(0,m) = m+1; \\ &A(n,0) = 1,\enspace\text{except } A(1,0)=2,\ A(2,0)=0; \\ &A(n+1,m+1) = A(n,A(n+1,m)) \end{align*}$$ 稍加計算可知, 該函數的第$0$層定義為 $A(0,m) = m+1$, 第$1$層為 $A(1,m)=m+2$, 第$2$層為 $A(2,m)=2m$, 第$3$層為 $A(3,m)=2^m$, 第$4$層從 $A(4,0)=1$ 開始, 每一步取冪 $A(4,m+1)=2^{A(4,m)}$, 得到 $m$ 層冪塔, 用 Knuth 箭頭來表示即為 $2\uparrow\uparrow m$. 由此可直觀地看出該函數隨層數增長速度之快.

Ackermann 函數的每一層級都是一個原始遞歸函數, 且每一個原始遞歸函數都以 Ackermann 函數的某一層級為上界, 因此對角 Ackermann 函數 $A(n)=A(n,n)$ 不是原始遞歸的.

一般遞歸函數

若 $k+1$ 元函數 $g$ 滿足根存在性條件, 則由如下 $k$ 元函數 $f$ 稱為 $g$ 由正則 $\mu$ 算子得到的:

$$f(n_1,\cdots,n_k)=\mu x\left[g(n_1,\cdots,n_k,x)=0\right]$$

在原始遞歸函數的基礎上進一步允許使用正則 $\mu$ 算子, 得到的函數稱為一般遞歸函數, 或簡稱遞歸函數. 遞歸函數集是最小的包含所有初始函數且對複合, 原始遞歸和正則 $\mu$ 算子封閉的函數集.

一般遞歸函數也是可計算的, 正則 $\mu$ 算子相當於有界搜索, 由於有根存在條件, 只需逐個代入自然數並檢測函數值是否為 $0$ 即可.

部分遞歸函數

如果去掉使用 $\mu$ 算子時對 “根存在條件” 的要求, 那麼得到的函數稱為部分遞歸函數 (或遞歸偏函數). 部分遞歸函數集是對一般遞歸函數集的進一步擴張, 它是最小的包含所有初始函數且對複合, 原始遞歸和 $\mu$ 算子封閉的函數集.

從程序角度看, $\mu$ 算子相當於無界搜索, 即從初始值開始逐個代入檢驗, 直到搜索得最小根. 一個函數滿足根存在性條件, 就意味著循環必定有終點 (停機), 這樣的函數就是一般遞歸函數; 而如果去除根存在性條件, 那麼這種循環就有可能永遠不會終止. 因此, 部分遞歸函數不一定處處有定義 (不一定是全函數).

一般地, 設 $g$ 為 $k+1$ 元部分函數, 對其使用 $\mu$ 算子得到函數 $f$: $$f(\alpha)=\mu x\left[\forall z\leq x\left(g(\alpha,z)\downarrow\right)\wedge g(\alpha,x)=0\right]$$ 則 $f$ 是一個部分遞歸函數. 其中 $\alpha$ 是 $n_1,\cdots,n_k$ 的縮寫; $g(\alpha,z)\downarrow$ 表示函數 $g$ 在點 $(\alpha,z)$ 有定義, 或稱 $g(\alpha,z)$ 收斂. 相應地, $g(\alpha,z)\uparrow$ 表示 $g$ 在該點無定義, 或稱 $g(\alpha,z)$ 發散.

上式中加入條件 $\forall z\leq x\left(g(\alpha,z)\downarrow\right)$ 是因為: $g(\alpha,x)$ 可以是部分函數, 有可能在最小根 $x_0$ 出現前, 就在某個 $z_0<x_0$ 處無定義. 事實上我們無法能行地 (在有限步內) 知道 $g(\alpha,z_0)$ 是發散的, 所以寧可達不到真正的根, 也不跳過發散點.

---

一般的 $\mu$ 算子可以作用在部分函數上, 也可以產生部分函數. 這種意義下的可計算函數可以不在所有輸入值上都有定義, 對某些輸入, 一個計算程序可能會一直運行, 永不停止. 由於這種特性, 部分遞歸函數能夠迴避上面使用的對角線證明, 達成對全體可計算函數的枚舉. 假定我們枚舉所有的部分遞歸函數: $f_0, f_1, \cdots$, 並定義對角函數 $F:\mathbb{N}\to\mathbb{N}$ 為 $F(n)=f_n(n)+1$, 則 $F$ 可以與列表中某個 $f_{k}$ 相同, 因為恰好 $f_k(k)$ 無定義 (全體部分遞歸函數可枚舉的嚴格證明需使用 Kleene 正規型定理).

可以證明, 部分遞歸的全函數一定是遞歸函數, 而 Ackermann 函數是部分遞歸的全函數, 從而是一個遞歸函數.

Church 論題: 算法可計算函數 $=$ 部分遞歸函數.

這不是一個定理, 而是一個經驗事實, 目前尚沒有發現反例.

形式算術的遞歸分析

遞歸關係和遞歸集

若 $k$ 元關係 $R$ 的特徵函數 $C_R$ 是遞歸函數, 則關係 $R$ 叫做遞歸關係. 一元遞歸關係叫做 $\mathbb{N}$ 的遞歸子集, 簡稱遞歸集.

例如, 二元關係 $\leq$, $=$, $<$ 都是遞歸關係, 因為

$$\begin{align*} &C_{\leq}(n,m) = \overline{\text{sg}}(n\dot{-}m) \\ &C_{=}(n,m) = \overline{\text{sg}}(n\ddot{-}m) \\ &C_{<}(n,m) = \text{sg}(n\dot{-}m) \end{align*}$$

若 $R$ 是 $k$ 元遞歸關係, 則 $\overline{R}$ 也是 $k$ 元遞歸關係, 其中 $\overline{R}=\mathbb{N}^k-R$: $$C_{\overline{R}}(n_1,\cdots,n_k) = 1-C_R(n_1,\cdots,n_k)$$ 若 $R_1$, $R_2$ 都是 $k$ 元遞歸關係, 則 $R_1\cup R_2$ 和 $R_1\cap R_2$ 也是 $k$ 元遞歸關係: $$\begin{align*} &C_{R_1\cup R_2}(n_1,\cdots,n_k) = \text{sg}\left(C_{R_1}(n_1,\cdots,n_k)+C_{R_2}(n_1,\cdots,n_k)\right)\\ &C_{R_1\cap R_2}(n_1,\cdots,n_k) = C_{R_1}(n_1,\cdots,n_k)\times C_{R_2}(n_1,\cdots,n_k) \end{align*}$$

設 $R$ 是 $k+1$ 元遞歸關係, 作如下 $k$ 元關係:

$$Q=\lbrace(n_1,\cdots,n_k):\exists x<n_k\enspace\text{s.t. }(n_1,\cdots,n_k,x)\in R\rbrace$$

則 $Q$ 也是遞歸關係, 因為

$$C_Q(n_1,\cdots,n_k)=\text{sg}\left(\sum_{x<n_k}C_R(n_1,\cdots,n_k,x)\right)$$ $\mathbb{N}$, $\emptyset$, 獨元集 $\left\{a\right\}$, 有限集 $\lbrace a_1,\cdots,a_n\rbrace$ 都是遞歸集. 因為: $C_{\mathbb{N}}\equiv1$, $C_{\emptyset}\equiv0$, $C_{\lbrace a\rbrace}=C_{=}(n,a)$, $\lbrace a_1,\cdots,a_n\rbrace=\bigcup_{i=1}^n \lbrace a_i\rbrace$.

---

定義二元關係 $\text{Divi}$: $(n,m)\in \text{Divi}$ $\Longleftrightarrow$ $n=0$ 或 $n\mid m$. 則 $\text{Divi}$ 是遞歸關係, 因為 $C_{\text{Divi}}(n,m)=\overline{\text{sg}}(\text{rem}(n,m))$.

全體素數的集 $\text{Prm}$ 是遞歸集. 用檢查因子個數的方式構造其特徵函數的遞歸形式, 若 $n$ 的因子數大於 $2$, 則 $n$ 不是素數, 所以有 (注意 $(0,n)\in\text{Divi}$ ):

$$C_{\text{Prm}}(n)=\left(4\dot{-}\sum_{i\leq n}C_{\text{Divi}}(i,n)\right)\times\text{sg}(n\dot{-}1)$$

設 $p(n)$ 定義為第 $n$ 個素數, 則 $p$ 是一元遞歸函數, 因為

$$\begin{align*} &p(0) = 2 \\ &p(n+1) = \mu x\left[C_{<}(p(n),x)\times C_{\text{Prm}}(x)=1\right] \end{align*}$$

遞歸函數的可表示性

定理: 遞歸函數在 $K_N$ 中皆可表示.

綜合上文的一些結論可知, $+$, $\times$, $\pi^k_i$, $C_{\leq}$ 四種函數及它們經有限次複合和使用 $\mu$ 算子得到的函數是可表示函數.

函數 $\mathsf{Z}$, $\mathsf{S}$, $\text{sg}$, $\overline{\text{sg}}$, $C_{=}$, $\dot{-}$, $\text{rem}$ 都是可表示函數. 因為:

• $\mathsf{S}(n)=n+C_{\leq}(n,n)$,
• $\mathsf{Z}(n)=C_{\leq}(n+1,n)=C_{\leq}(\mathsf{S}(n),n)$,
• $\text{sg}(n)=C_{\leq}(1,n)=C_{\leq}(\mathsf{S}(\mathsf{Z}(n)),n)$,
• $\overline{\text{sg}}(n)=C_{\leq}(n,\mathsf{Z}(n))$,
• $C_{=}(n,m)=C_{\leq}(n,m)\times C_{\leq}(m,n)$,
• $n\dot{-}m=\mu x\left[\overline{\text{sg}}\left(C_{\leq}(n,m+x)\right)=0\right]$,
• $\text{rem}(n,m)=\text{sg}(n)\times(m\dot{-}(n\times(\mu x\left[\text{sg}(n)\times C_{\leq}(n\times x,m)=0\right]\dot{-}1)))$.

---

接下來只要證明可表示函數對原始遞歸封閉即可. 由於形式系統中不能有無限步的歸納, 我們必須對歸納的過程值進行編碼, 把任意長度的序列 “壓縮” 進單個值, 隨後再把計算所需信息 “解碼” 出來.

然而問題在於, 我們一般用於編碼的指數函數和素因數分解, 其定義本身就用到了原始遞歸. 為避免循環, Gödel 巧妙地利用了中國剩餘定理. (注意, 上文已經證明了 $\text{rem}$ 可表示)

引理1: 定義 Gödel 函數 $\beta(b,c,i)=\text{rem}(1+(i+1)b,c)$, 則 $\beta$ 是 $K_N$ 的可表示函數, 且對於給定的 $a_0,\cdots,a_m\in\mathbb{N}$, 一定存在 $b,c\in\mathbb{N}$, $b\le c$, 滿足 $\beta(b,c,i)=a_i$, 其中 $i=0,\cdots,m$.

證明: 令 $s=\max\lbrace a_0,\cdots,a_m,m\rbrace$, 取 $b=s!$, 則 $1+b,\cdots,1+(m+1)b$ 兩兩互素. 由中國剩餘定理知 $\text{rem}(1+(i+1)b,c)=a_i$, $i=0,\cdots,m$ 有解. $\square$

引理2: 如下函數是可表示函數: $$\begin{align*} \text{pair}(b,c) &:= \frac{1}{2}(b+c)\times(b+c+1)+b \\ \text{fst}(d) &:=\mu x\left[\exists y<d(\text{pair}(x,y)=d)\right] \\ \text{snd}(d) &:=\mu y\left[\exists x<d(\text{pair}(x,y)=d)\right] \end{align*}$$

$\text{pair}$ 是著名的 Cantor 配對函數, 它是一個 $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 的雙射, 這保證了根存在條件 (在此其實並不關鍵). 令 $d=\text{pair}(b,c)$, 則 $b=\text{fst}(d)$, $c=\text{snd}(d)$. 這三個函數的作用是把 $b$ 和 $c$ 進一步 "壓縮" 到單個值.

令 $\gamma(d,i)=\beta(\text{fst}(d),\text{snd}(d),i)$, 由引理1知, 任給 $a_0,\cdots,a_m\in\mathbb{N}$, 必存在 $d$ 使得 $\gamma(d,i)=a_i$, $i=0,\cdots,m$.

命題: $K_N$ 的可表示函數對原始遞歸封閉.

證明: 設 $k+1$ 元函數 $f$ 滿足 $$\begin{align*} &f(\alpha,0) = g(\alpha) \\ &f(\alpha,m+1) = h\left(\alpha,m,f(\alpha,m)\right) \end{align*}$$ 其中 $g$, $h$ 是可表示函數, $\alpha$ 是 $n_1,\cdots,n_k$ 的縮寫.

定義如下關係

$$R(\alpha,m,d):=(\gamma(d,0)=g(\alpha))\wedge\forall i<m\left(\gamma(d,i+1)=h(\alpha,m,\gamma(d,i))\right)$$

則 $R$ 是可表示的, 從而 $R$ 的特徵函數 $C_R$ 也可表示. 令

$$F(\alpha,m):=\mu d\left[C_R(\alpha,m,d)=1\right]$$

則 $F$ 也可表示. 取 $a_i=f(\alpha,i)$, $i=0,\cdots,m$, 據引理1, $F$ 滿足根存在條件, 可知 $F$ 是良好定義的全函數. 最後令 $f(\alpha,m)=\gamma(F(\alpha,m),m)$ 即可. $\square$

由此可知, 任意遞歸函數都是可表示函數. 一個明顯的推論是: 任意遞歸關係在 $K_N$ 中可表示.

語法的算術化

Gödel 配數

證明 Gödel 不完備性定理的一個關鍵步驟是對形式語言 $K_N$ (有限符號串) 進行編碼 (配數), 使 $K_N$ 算術化, 以便之後讓 $K_N$ 從內部 “談論自身”. 配數的方法有很多種, 下面是其中一種.

首先, 給每個字母 $u$ 指定一個 Gödel 數 $\text{g}(u)$ 如下:

$$\begin{array}{c|ccccccccc} u & \mathsf{S} & + & \times & \neg & \to & \forall &\approx & \overline{0} & x_i \\ \hline \text{g}(u) & 1 & 3 & 5 & 7& 9 & 11 & 13 & 15 & 15+2i \\ \end{array}$$

字母串 $u_0 u_1\cdots u_k$ 的 Gödel 數定義為: $$\text{g}(u_0 u_1\cdots u_k) = \langle u_0 u_1\cdots u_k\rangle := 2^{\text{g}(u_0)}\thinspace 3^{\text{g}(u_1)}\cdots\thinspace p_k^{\text{g}(u_k)}$$ 其中 $p_k$ 是第 $k$ 個素數. 規定空序列的 Gödel 數為 $\langle\ \rangle=1$.

字母串的 Gödel 數與字母的 Gödel 數不會相同, 因為前者是偶數, 後者是奇數; 由自然數的唯一分解性, 不同字母串的 Gödel 數也不會相同.

設 $\tau_0,\cdots,\tau_n$ 是字母串的一個有限序列, 則該序列的 Gödel 數定義為:

$$\text{g}(\tau_0,\cdots,\tau_n) = \langle\tau_0,\cdots,\tau_n\rangle := 2^{\text{g}(\tau_0)}\thinspace 3^{\text{g}(\tau_1)}\cdots\thinspace p_n^{\text{g}(\tau_n)}$$

容易驗證, 這種擴張保持單射性.

編碼相關的遞歸函數

上文已表明, 整除關係 $\text{Divi}$ 是遞歸關係, 素數集 $\text{Prm}$ 是遞歸集, 一元函數 $p_n$ 是遞歸函數.

當 $n>1$ 時, 設 $n=2^{e_0}\thinspace 3^{e_1}\cdots\thinspace p_k^{e_k}$, 則如下定義的函數是遞歸的:

$$(n)_{m}=\begin{cases} e_{m}, &n>1 \\ 0, & n=0\enspace\text{or}\enspace n=1 \end{cases}$$

因為

$$(n)_{m}=\mu x\left[\text{sg}(n)\times\overline{\text{sg}}(\text{rem}(p_{m}^{x+1},n))=0\right]$$

定義一元函數 $\text{lh}$: 若 $n=0$ 或 $1$, 則 $\text{lh}(n)=0$; 若 $n>1$, 則 $\text{lh}(n)$ 為 $n$ 的素因子的個數. 函數 $\text{lh}$ 是遞歸的, 因為

$$\text{lh}(n)=\sum_{x\leq n}\left(C_{\text{Prm}}(x)\times C_{\text{Divi}}(x,n)\right)$$

稱 $\text{lh}$ 為長度函數, 因為對任何 $n=\langle u_0\cdots u_k\rangle$ 有 $\text{lh}(n)=k+1$.

---

二元並接函數 $\ast$ 定義為 $$n \ast m = n\times\prod_{x<\text{lh}(m)}p_{\text{lh}(n)+x}^{(m)_x}$$

設 $n=2^{a_0}\thinspace 3^{a_1}\cdots\thinspace p_k^{a_k}$, $m=2^{b_0}\thinspace 3^{b_1}\cdots\thinspace p_l^{b_l}$, 且 $a_0,\cdots,a_k$ 皆非零, 則

$$n \ast m = 2^{a_0}\thinspace 3^{a_1}\cdots\thinspace p_k^{a_k}\thinspace p_{k+1}^{b_0}\thinspace p_{k+2}^{b_1}\cdots\thinspace p_{k+l+1}^{b_l}$$

即 $n=\langle r_0\cdots r_k\rangle$, $m=\langle s_0\cdots s_l\rangle$ $\Longrightarrow$ $n\ast m=\langle r_0\cdots r_k s_1\cdots s_l\rangle$.

由 $(n)_{m}$ 和 $\text{lh}$ 的定義知, 函數 $\ast$ 也是遞歸的.

---

對 $k+1$ 元全函數 $f$, 定義 $f$ 的歷史函數 $F$:

$$F(\alpha,n)=\prod_{x\le n}p_x^{f(\alpha,x)}=p_0^{f(\alpha,0)}p_1^{f(\alpha,1)}\cdots p_{n}^{f(\alpha,n)}$$

稱 $k+1$ 元函數 $f$ 是由 $g$ 和 $h$ 經強遞歸得到的, 如果 $$\begin{align*} &f(\alpha,0)=g(\alpha) \\ &f(\alpha,n+1)=h(\alpha,n,F(\alpha,n)) \end{align*}$$

命題: 如果 $f$ 是由 $g$ 和 $h$ 經強遞歸得到的, 且 $g$ 和 $h$ 都是原始遞歸函數, 則 $f$ 也是原始遞歸的.

證明: 只需證明 $F$ 是原始遞歸的. 事實上,

$$\begin{align*} &F(\alpha,0) = 1, \\ &F(\alpha,n+1) = F(\alpha,n)\times p_{n+1}^{h(\alpha,n,F(\alpha,n))} \end{align*}$$

從而 $f(\alpha,n)=(F(\alpha,n))_n$ 也是原始遞歸的. $\square$

該命題給出了在遞歸定義中引用任何已有項的合法性.

形式算術的遞歸性質

一元函數 $\text{Num}$ 定義為 $\text{Num}(n)=\text{g}(\overline{n})$, 則 $\text{Num}$ 是遞歸函數, 因為

$$\begin{align*} &\text{Num}(0) = \text{g}(\overline{0}) = 2^{15} \\ &\text{Num}(n+1) = 2^1 \ast \text{g}(\overline{n}) = 2^1 \ast \text{Num}(n) \end{align*}$$

命題: $\mathbb{N}$ 的以下子集是遞歸集:

• $\text{VS}=\lbrace2^{15+2k}:k\ge 1\rbrace$: 所有個體變元的 Gödel 數構成的集,
• $\text{TM}$: 所有 $K_N$ 的項的 Gödel 數構成的集,
• $\text{YF}$: 所有 $K_N$ 的原子公式的 Gödel 數構成的集,
• $\text{FM}$: 所有 $K_N$ 的公式的 Gödel 數構成的集.

證明: $\text{VS}$ 的特徵函數很容易構造; 另外三個集的特徵函數使用強遞歸條件引用已有項即可. $\square$

---

對於 $i=1,\cdots,5$, 把所有 $\text{(Ki)}$ 型公理的 Gödel 數構成的集記作 $\text{LA}_i$.

容易證明 $\text{LA}_1$, $\text{LA}_2$, $\text{LA}_3$ 的遞歸性. 而要證明 $\text{LA}_4$ 和 $\text{LA}_5$ 的遞歸性, 難點在於表達如下關係: 在 Gödel 數為 $n_3$ 的項 $u(x_i)$ 或公式 $\varphi(x_i)$ 中, 用 Gödel 數為 $n_2$ 的項 $t$ 去替換 Gödel 數為 $n_1$ 的變元 $x_i$ 的所有自由出現, 所得結果 $u(t)$ 或 $\varphi(t)$ 的 Gödel 數是 $n_4$.

令 $\gamma=2^{n_3}\thinspace 3^{n_4}\cdots$, 則 $(\gamma)_0=n_3$, $(\gamma)_1=n_4$, 藉此將 $n_1$, $n_2$, $n_3$, $n_4$ 的四元關係轉化為一個三元關係.

定義三元關係 $\text{SBS}$: $(n_1,n_2,\gamma)\in\text{SBS}$ $\Longleftrightarrow$ $n_1\in\text{VS}$, $n_2\in\text{TM}$, $(\gamma)_0\in\text{TM}\cup\text{FM}$, $(\gamma)_1$ 是用 $n_2$ (對應的) 項去替換 $(\gamma)_0$ 項或 $(\gamma)_0$ 公式中的 $n_1$ 變元的全部自由出現所得結果的 Gödel 數.

通過分析用項 $t$ 去替換項 $u(x_i)$ 或公式 $\varphi(x_i)$ 中所有自由的 $x_i$ 所得的可能類型, 可以逐個寫出關係 $\text{SBS}$ 需滿足的約束條件, 從而用強遞歸寫出 $C_{\text{SBS}}$ 的特徵函數, 表明 $\text{SBS}$ 是遞歸關係. 證明細節略過.

在 $\text{SBS}$ 的基礎上, 定義三元函數 $\text{Sub}$: $$\text{Sub}(n_1,n_2,n_3)=\mu x\left[C_{\text{SBS}}\left(n_1,n_2,2^{n_3}\thinspace 3^{x}\right)+C_{\leq}\left((p_{n_2 n_3})^{n_2^2 n_3^2},x\right)=1 \right]$$

在函數 $\text{Sub}$ 中加一項 $C_{\leq}(m,x)$ 是為了確保根存在性條件, $m$ 需要取得充分大, 以至於不可能是上述替換結果的 Gödel 數, 這裡取 $m=(p_{n_2 n_3})^{n_2^2 n_3^2}$. 函數 $\text{Sub}$ 顯然是遞歸的.

根據定義, 可以把上式具體寫作:

$$\text{Sub}(n_1,n_2,n_3)=\begin{cases} \text{g}(u(t)), &\text{if}\enspace n_1=\text{g}(x_i),\thinspace n_2=\text{g}(t),\thinspace n_3=\text{g}(u(x_i)); \\ \text{g}(\varphi(t)), &\text{if}\enspace n_1=\text{g}(x_i),\thinspace n_2=\text{g}(t),\thinspace n_3=\text{g}(\varphi(x_i)); \\ (p_{n_2 n_3})^{n_2^2 n_3^2},&\text{otherwise}. \end{cases}$$

---

命題: 如下關係是遞歸關係:

1. $\text{FR}=\lbrace(n_1,n_2):n_1$ 變元在 $n_2$ 項或 $n_2$ 公式中自由出現 $\rbrace$
2. $\text{FRT}=\lbrace(n_1,n_2,n_3):n_2$ 項對 $n_3$ 公式中的 $n_1$ 變元是自由的 $\rbrace$

證明:

1. 用不同於 $n_1$ 變元 $x_i$ 的另一變元, 例如 $x_{i+1}$ (注意有 $\text{g}(x_{i+1})=n_1\times 2^2$ ), 去替換 $n_2$ 項或 $n_2$ 公式中所有自由出現的 $x_i$, 所得結果發生變化, 則說明 $n_1$ 變元在 $n_2$ 項或 $n_2$ 公式中自由出現. 於是有

$$(n_1,n_2)\in\text{FR}\Longleftrightarrow n_1\in\text{VS}\wedge n_2\in\text{TM}\cup\text{FM}\wedge(n_1,n_1\times 2^2,2^{n_2}\thinspace 3^{n_2})\not\in\text{SBS}$$

2. 分情況用強遞歸寫出 $C_{\text{FRT}}$, 細節略. $\square$

由 $\text{Sub}$, $\text{FR}$, $\text{FRT}$ 的遞歸性可得 $\text{LA}_4$ 和 $\text{LA}_5$ 的遞歸性.

從而 $\text{LA}=\text{LA}_1\cup\cdots\cup\text{LA}_5$ 是遞歸集, 即 $K_N$ 的所有邏輯公理的 Gödel 數構成的集是遞歸集.

令 $\text{EA}_i$ 為 $\text{(Ei)}$ 型等詞公理的 Gödel 數構成的集, $\text{NA}_i$ 為 $\text{(Ni)}$ 型算術公理的 Gödel 數構成的集. 仿照上面的分析可以得到 $\text{EA}_i$ 和 $\text{NA}_i$ 的遞歸性.

從而 $\text{PA}$ ($=\text{EA}_1\cup\cdots\cup\text{EA}_3\cup\text{NA}_1\cup\cdots\cup\text{NA}_7$) 也是遞歸集, 即 $\mathcal{N}$ 中公式的 Gödel 數集是遞歸集. 進而, $\text{AX}=\text{LA}\cup\text{PA}$ 是遞歸集, 即包括邏輯公理和算術公理在內的所有 $K_N$ 公理的 Gödel 數構成的集是遞歸集.

如下關係或集是遞歸的:

• $\text{MP}=\lbrace(n_1,n_2,n_3):n_1=\text{g}(\varphi),n_2=\text{g}(\varphi\to\psi),n_3=\text{g}(\psi)\rbrace$,
• $\text{GEN}=\lbrace(n_1,n_2):n_1=\text{g}(\varphi),n_2=\text{g}(\forall x_i\varphi)\rbrace$,
• $\text{PF}=\lbrace n:n$ 是從 $\mathcal{N}$ 的證明的 Gödel 數 $\rbrace$,
• $\text{PRF}=\lbrace(n,m):m=\text{g}(\varphi)$, $n$ 是 $\varphi$ 從 $\mathcal{N}$ 的證明的 Gödel 數 $\rbrace$.

這裡 $\text{PF}$ 的遞歸性僅僅依賴於 “$\text{AX}$ 是遞歸的” 這一點, 而與 $\text{AX}$ 中包含哪些具體公理的 Gödel 數無關. 不論怎樣增減公理, 只要不改變 $\text{AX}$ 的遞歸性, 就不改變 $\text{PF}$ 的遞歸性.

$\text{AX}$ 和 $\text{PF}$ 都是遞歸集, 所以根據 Church 論題, 存在能行算法可用來判定任意有限字母串是不是 $\mathcal{N}$ 的公理, 以及任給的有限公式序列是不是從 $\mathcal{N}$ 的一個證明. 我們稱這樣的理論是遞歸可公理化的.

下一篇: Gödel 不完備性定理和 Turing 機