數理邏輯筆記 No.3

上一篇: 謂詞演算

形式算術

等詞

在上一篇定義的謂詞演算基礎上, 我們引入一個特殊的二元謂詞: 等詞 $R^2_1$, 這個謂詞用以形式化表達我們心目中的 “相等” 概念, 形式算術 $K_N$ 即是一種帶等詞的謂詞演算. 下面把 $R^2_1$ 簡記為 “$\approx$”.

在帶有等詞的謂詞演算 $K$ 中, 以下三種形式的公式叫做等詞公理:

$$\begin{align*} &(E1)\quad t\approx t; \\ &(E2)\quad t_k\approx u\to R^2_1(f^n_i(t_1,\cdots,t_k,\cdots,t_n),f^n_i(t_1,\cdots,u,\cdots,t_n)); \\ &(E3)\quad t_k\approx u\to (R^n_i(t_1,\cdots,t_k,\cdots,t_n)\to R^n_i(t_1,\cdots,u,\cdots,t_n)). \end{align*}$$

其中 $t_1,\cdots,t_n$ 是任意的項, $k=1,\cdots,n$. 記 $E=\left\lbrace E1,E2,E3\right\rbrace$.

需要注意的是, 這些等詞公理不是有效式, 即它並非在 $K$ 的任何解釋域中恆真. 但當 “$\approx$” 在解釋域中解釋為 “相等” 時, 該解釋域一定是 $E$ 的模型.

容易證明:

1. $E\vdash t\approx t$; (自反性)
2. $E\vdash t\approx u\to u\approx t$; (對稱性)
3. $E\vdash t\approx u\to(u\approx v\to t\approx v)$. (傳遞性)

由此可知, 等詞 “$\approx$” 在公理集 $E$ 的模型中不一定解釋為 “相等”, 但它所解釋的二元關係一定是等價關係.

形式算術

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

$K_N$ 有一個自然的解釋域: 自然數集 $\mathbb{N}=\left\lbrace 0,1,2,\cdots\right\rbrace$. 在 $\mathbb{N}$ 中 $c_1$ 解釋為 $0$; $f^1_1$, $f^2_1$, $f^2_2$ 分別解釋為一元後繼函數, 二元求和函數, 二元乘積函數; 等詞 $\approx$ 解釋為 $\mathbb{N}$ 中的相等($=$).

由於接下來的討論基本限於這個標準自然數的解釋域, 下面把個體常元 $c_1$ 寫成 $\overline{0}$, $f^1_1(t)$, $f^2_1(t_1,t_2)$, $f^2_2(t_1,t_2)$ 分別寫成 $t'$, $t_1+t_2$, $t_1\times t_2$. 在 $\mathbb{N}$ 中常元 $\overline{0}$ 解釋為 $0$, 項 $\overline{0}'$ 解釋為 $0'=1$. 下面把閉項 $\overline{0}',\overline{0}'',\cdots$ 分別寫作 $\overline{1},\overline{2},\cdots$, 這些形為 $\overline{n}$ 的閉項叫做 $K_N$ 的數字.

$K_N$ 中所有等詞公理及如下形式的公式都叫做算術公理: $$\begin{align*} &(N1)\quad t'\not\approx \overline{0}; \\ &(N2)\quad t_1'\approx t_2'\to t_1\approx t_2; \\ &(N3)\quad t+\overline{0}\approx t; \\ &(N4)\quad t_1+t_2'\approx (t_1+t_2)'; \\ &(N5)\quad t\times\overline{0}\approx \overline{0}; \\ &(N6)\quad t_1\times t_2'\approx t_1\times t_2+t_1; \\ &(N7)\quad p(\overline{0})\to(\forall x(p(x)\to p(x'))\to\forall x\thinspace p(x)). \end{align*}$$

其中 $p(x)$ 是任意的公式.

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

若 $\mathcal{N}\vdash p$, 則稱 $p$ 為 Peano 形式算術的(形式)定理. 通常的關於自然數的定理可以大量翻譯成形式定理, 但其形式證明一般都很複雜. “建立形式算術的主要目的之一, 是用以探討關於自然數的性質, 我們究竟能精確而機械地抓住些什麼.”

可表示函數與關係

函數

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

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

事實上, 定義中的 (2) 可由 (1) 和 (3) 推出, 所以 (1)+(3) 給出了函數 $f$ 用公式 $p$ 在 $K_N$ 中可表示的充要條件.

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

---

定義 $k$ 元投影函數 $\text{p}^k_i$:

$$\text{p}^k_i(n_1,\cdots,n_k)=n_i,\quad (i=1,\cdots,k)$$

則函數 $+$, $\times$, $\text{p}^k_i$ 在 $K_N$ 中是可表示的:

1. 二元和函數 $+$ 由公式 $x_1+x_2\approx y$ 表示;
2. 二元乘積函數 $\times$ 由公式 $x_1\times x_2\approx y$ 表示;
3. $\text{p}^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$ 分別用公式

$$q(x_1,\cdots,x_j,y),\thinspace r_1(x_1,\cdots,x_k,y),\thinspace \cdots,\thinspace r_j(x_1,\cdots,x_k,y)$$

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

$$\exists y_1\cdots\exists y_j\thinspace (r_1(x_1,\cdots,x_k,y_1)\wedge\cdots\wedge r_j(x_1,\cdots,x_k,y_j)\wedge q(y_1,\cdots,y_j,y))$$

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

關係

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

1. $(n_1,\cdots,n_k)\in R$ $\Rightarrow$ $\mathcal{N}\vdash p(\overline{n_1},\cdots,\overline{n_k})$;
2. $(n_1,\cdots,n_k)\not\in R$ $\Rightarrow$ $\mathcal{N}\vdash\neg p(\overline{n_1},\cdots,\overline{n_k})$.

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

---

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

若關係 $R$ 用公式 $p(x_1,\cdots,x_k)$ 可表示, 則 $C_R$ 可用如下公式表示:

$$(p(x_1,\cdots,x_k)\wedge y\approx 1)\vee(\neg p(x_1,\cdots,x_k)\wedge y\approx 0)$$

若 $C_R$ 用公式 $p(x_1,\cdots,x_k,y)$ 可表示, 則 $R$ 用如下公式可表示:

$$p(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\lbrace x:g(n_1,\cdots,n_k,x)=0\right\rbrace$$

即 $f(n_1,\cdots,n_k)$ 是使 $g(n_1,\cdots,n_k,x)$ 的 $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$ 中可用 $q(x_1,\cdots,x_{k+1},y)$ 表示, 則對 $g$ 使用 $\mu$ 算子得到的 $k$ 元函數 $f$ 在 $K_N$ 中用如下公式表示: $$q(x_1,\cdots,x_k,y,\overline{0})\wedge\forall x (q(x_1,\cdots,x_k,x,\overline{0})\to y\leq x)$$

其中 $x$ 取不在 $q(x_1,\cdots,x_k,y,\overline{0})$ 中出現的變元. 這個公式的含義在直觀上是很明顯的.

遞歸函數

遞歸函數是一類重要的數論函數, 也是遞歸論的研究對象, 直觀來看, 遞歸函數即是可計算函數之概念的精確化 (因此, 遞歸論也叫可計算性理論).

一般遞歸函數

首先定義三種基本函數:

1. 一元零函數 $z$, $z(n)=0$;
2. 一元後繼函數 $s$, $s(n)=n+1$;
3. $k$ 元投影函數 $\text{p}^k_i$, $\text{p}^k_i(n_1,\cdots,n_k)=n_i$, $i=1,\cdots,k$.

基本函數以及由它們經過有限次使用下面的規則 I, II, III 得到的函數叫做遞歸函數 (或一般遞歸函數).

規則 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)$$

規則 II ——遞歸
由 $k$ 元函數 $g$ 和 $k+2$ 元函數 $h$ 使用遞歸規則生成 $k+1$ 元函數 $f$

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

特別地, 當 $k=0$ 時

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

規則 III ——$\mu$ 算子
若 $k+1$ 元函數 $g$ 滿足根存在性條件, 則由 $g$ 使用 $\mu$ 算子生成 $k$ 元函數 $f$

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

若去掉規則 III, 只允許使用規則 I, II, 則定義的函數叫做原始遞歸函數. 原始遞歸函數是有窮主義數學的基礎. 最早由 Skolem 提出用以形式化有窮主義數學的原始遞歸算術 (Primitive Recursive Arithmetic, $\text{PRA}$) 就只能表達關於自然數和原始遞歸函數的命題. $\text{PRA}$ 經常被用作證明論的基本形式系統.

若去掉規則 III 中根存在性條件的限制, 則定義的函數叫做部分遞歸函數 (或遞歸偏函數). 部分遞歸函數不一定處處有定義, 所以不一定是全函數.

---

命題: 由 $k$ 元遞歸函數 $f$ 用下式定義的 $l$ 元函數 $g$ 也是遞歸的: $$g(n_1,\cdots,n_l)=f(n_{m_1},\cdots,n_{m_k})$$ 其中 $1\leq m_i\leq l$. 這是因為, $g$ 可由如下複合而成: $$g(n_1,\cdots,n_l)=f(p^l_{m_1}(n_1,\cdots,n_l),\cdots,p^l_{m_k}(n_1,\cdots,n_l))$$ 該命題可由於 "增元" 或 "減元".

下面列舉一些常用的(原始)遞歸函數:

1. $k$ 元常值函數 $c_m$, $c_m(n_1,\cdots,n_k)=m$.

$$\begin{align*} &c_0(n_1,\cdots,n_k) = z(p^k_1(n_1,\cdots,n_k)), \\ &c_{m+1}(n_1,\cdots,n_k) = s(c_m(n_1,\cdots,n_k)) \end{align*}$$

2. 二元和函數 $+$

$$\begin{align*} &n_1+0 = p^1_1(n_1), \\ &n_1+(n+1) = (n_1+n)+1 = s(p^3_3(n_1,n,n_1+n)) \end{align*}$$

3. 二元乘積函數 $\times$

$$\begin{align*} &n_1\times 0 = z(n_1), \\ &n_1\times (n+1) = p^3_3(n_1,n,n_1\times n)+p^3_1(n_1,n,n_1\times n) \end{align*}$$

4. 前鄰函數 $p^{-}$, 若 $n=0$ 則 $p^{-}(n)=0$, 否則 $p^{-}(n)=n-1$.

$$\begin{align*} &p^{-}(n) = 0, \\ &p^{-}(n+1) = n = p^2_1(n,p^{-}(n)) \end{align*}$$

5. 截差函數 $\dot{-}$, 若 $n_1\geq n_2$, 則 $n_1\dot{-}n_2=n_1-n_2$, 否則 $n_1\dot{-}n_2=0$.

$$\begin{align*} &n_1\dot{-}\thinspace 0 = n_1 = p^1_1(n_1) , \\ &n_1\dot{-}(n+1) = p^{-}(n_1\dot{-}n) = p^{-}(p^3_3(n_1,n,n_1\dot{-}n)) \end{align*}$$

6. 一元函數 $\text{sg}$, 若 $n=0$ 則 $\text{sg}(n)=0$, 否則 $\text{sg}(n)=1$.

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

7. 一元函數 $\overline{\text{sg}}$, $\overline{\text{sg}}(n)=1\dot{-}\text{sg}(n)$.

8. 絕對差 $\ddot{-}$, $n_1\ddot{-}n_2=|n_1-n_2|$.

$$n_1\ddot{-}n_2=(n_1\dot{-}n_2)+(n_2\dot{-}n_1)$$

9. $k$ 元最值函數 $\min$, $\max$.

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

10. 指數函數 $n_1^{n_2}$, 規定 $0^0=0$.

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

11. 餘數函數 $\text{rem}$, 若 $n_1>0$, $\text{rem}(n_1,n_2)$ 是用 $n_1$ 除 $n_2$ 所得餘數; 若 $n_1=0$ 則 $\text{rem}(n_1,n_2)=0$.

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

12. 設 $f$ 是 $k+1$ 元遞歸函數, 由 $f$ 定義新的 $k$ 元函數 $g$ 和 $k+1$ 元函數 $h$:

$$\begin{align*} &g(n_1,\cdots,n_k) = \sum_{i\leq n_k} f(n_1,\cdots,n_k,i), \\ &h(n_1,\cdots,n_{k+1}) = \sum_{i\leq n_{k+1}} f(n_1,\cdots,n_k,i) \end{align*}$$

則 $g$ 和 $h$ 都是遞歸的, 因為

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

13. 設 $f$ 是 $k+1$ 元遞歸函數, 定義新的 $k$ 元函數 $g$ 和 $k+1$ 元函數 $h$:

$$\begin{align*} &g(n_1,\cdots,n_k) = \sum_{i < n_k} f(n_1,\cdots,n_k,i), \\ &h(n_1,\cdots,n_{k+1}) = \sum_{i < n_{k+1}} f(n_1,\cdots,n_k,i) \end{align*}$$

($n_k=0$ 時, 規定 $g=0$; $n_{k+1}=0$ 時, 規定 $h=0$. )

14. 設 $f$ 是 $k+1$ 元遞歸函數, 定義新的 $k$ 元函數 $g$ 和 $k+1$ 元函數 $h$:

$$\begin{align*} &g(n_1,\cdots,n_k) = \prod_{i\leq n_k} f(n_1,\cdots,n_k,i), \\ &h(n_1,\cdots,n_{k+1}) = \prod_{i\leq n_{k+1}} f(n_1,\cdots,n_k,i) \end{align*}$$

($n_k=0$ 時, 規定 $g=1$; $n_{k+1}=0$ 時, 規定 $h=1$. )

可計算的非原始遞歸函數

我們可以列舉原始遞歸函數的生成序列, 從而系統地枚舉原始遞歸函數. 令 $g_0, g_1, \cdots$ 是這樣枚舉出的原始遞歸函數序列, 定義函數 $F:\mathbb{N}\to\mathbb{N}$ 為 $F(n)=g_n(n)+1$, 則 $F$ 顯然不同於任何一個已列出的原始遞歸函數, 所以它不是原始遞歸的. 但直觀來看, 這個函數明顯是可計算的.

一個更具體的例子是 Ackermann 函數 $A(n,m)$, 定義為:
$$\begin{array}{rl}{\displaystyle }& {\displaystyle A(0,m)=m+1;}\\ {\displaystyle }& {\displaystyle A(n,0)=1,\text{except}A(1,0)=2,A(2,0)=0;}\\ {\displaystyle }& {\displaystyle A(n+1,m+1)=A(n,A(n+1,m))}\end{array}$$
\begin{align*}
&A(0,m) = m+1; \
&A(n,0) = 1,\quad\text{except}\enspace A(1,0)=2,\thinspace 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$ 元關係 $R$ 的特徵函數 $C_R$ 是遞歸函數, 則關係 $R$ 叫做遞歸關係. 一元遞歸關係叫做 $\mathbb{N}$ 的遞歸子集, 簡稱遞歸集.

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

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

若 $R$ 是 $k$ 元遞歸關係, 則 $\overline{R}$ 也是 $k$ 元遞歸關係, 其中 $\overline{R}=\mathbb{N}^k-R$.
若 $R_1$, $R_2$ 都是 $k$ 元遞歸關係, 則 $R_1\cup R_2$ 和 $R_1\cap R_2$ 也是 $k$ 元遞歸關係.

$$\begin{align*} &C_{\overline{R}}(n_1,\cdots,n_k) = 1-C_R(n_1,\cdots,n_k) \\ &C_{R_1\cup R_2}(n_1,\cdots,n_k) = \text{sg}(C_{R_1}(n_1,\cdots,n_k)+C_{R_2}(n_1,\cdots,n_k))\\ &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=\left\lbrace (n_1,\cdots,n_k):\exists x<n_k\enspace \text{s.t.}\enspace (n_1,\cdots,n_k,x)\in R\right\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}$, $\varnothing$, 獨元集 $\left\lbrace a\right\rbrace$, 有限集 $\left\lbrace a_1,\cdots,a_n\right\rbrace$ 都是遞歸集. 因為 $C_{\mathbb{N}}=1$, $C_{\varnothing}=0$, $C_{\left\lbrace a\right\rbrace}=C_{=}(n,a)$, $\left\lbrace a_1,\cdots,a_n\right\rbrace=\bigcup_{i=1}^n \left\lbrace a_i\right\rbrace$.

---

定義二元關係 $\text{Divi}$, $(n_1,n_2)\in \text{Divi}$ 當且僅當 $n_1=0$ 或 $n_1$ 整除 $n_2$. 則 $\text{Divi}$ 是遞歸關係, 因為 $C_{\text{Divi}}(n_1,n_2)=\overline{\text{sg}}(\text{rem}(n_1,n_2))$.
進而, 全體素數的集 $\text{Prm}$ 是遞歸集. 我們用檢查因子個數的方式構造其特徵函數的遞歸形式, 若 $n$ 的因子數大於 $2$, 則 $n$ 不是素數, 所以有:

$$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(0)=2$, $p(1)=3$, $\cdots$ ), 則 $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$ 中皆可表示. 這一結論在 Gödel 不完備性定理的證明中起重要作用.

先引入三個記號: $\text{REP}$, $\text{REC}$, $\text{REC}^{*}$.

1. $\text{REP}$: 在 $K_N$ 中可表示的函數全體構成的集;
2. $\text{REC}$: 遞歸函數全體構成的集;
3. $\text{REC}^{*}$: $+$, $\times$, $\text{p}^k_i$, $C_{\leq}$ 四種函數及它們經有限次使用複合(規則 I)和 $\mu$ 算子(規則 III)得到的函數的全體所構成的集合.

綜合上文的一些結論, 顯然有 $\text{REC}^{*}\subseteq\text{REC}$, $\text{REC}^{*}\subseteq\text{REP}$. 則只需要證明 $\text{REC}\subseteq\text{REC}^{*}$ 即得到遞歸函數的可表示性.

首先, 函數 $z$, $s$, $\text{sg}$, $\overline{\text{sg}}$, $C_{=}$, $\dot{-}$, $\text{rem}$ 都屬於 $\text{REC}^{*}$. 因為:

1. $s(n)=n+C_{\leq}(n,n)=p^1_1(n)+C_{\leq}(p^1_1(n),p^1_1(n))$;
2. $z(n)=C_{\leq}(n+1,n)=C_{\leq}(s(n),p^1_1(n))$;
3. $\text{sg}(n)=C_{\leq}(1,n)=C_{\leq}(s(z(n)),p^1_1(n))$;
4. $\overline{\text{sg}}(n)=C_{\leq}(p^1_1(n),s(z(n)))$;
5. $C_{=}(n_1,n_2)=C_{\leq}(n_1,n_2)\times C_{\leq}(p^2_2(n_1,n_2),p^2_1(n_1,n_2))$;
6. $n_1\dot{-}n_2=\mu x\left[\overline{\text{sg}}(C_{\leq}(n_1,n_2+x))=0\right]$;
7. $\text{rem}(n_1,n_2)=\text{sg}(n_1)\times(n_2\dot{-}(n_1\times(\mu x\left[\text{sg}(n_1)\times C_{\leq}(n_1\times x,n_2)=0\right]\dot{-}1)))$.

上面的式子有的還可以進一步展開, 但是沒有必要.

接下來只要證明 $\text{REC}^{*}$ 對規則 II 封閉, 即由 $\text{REC}^{*}$ 中兩個函數 $g$, $h$ 使用規則 II 得到的函數仍在 $\text{REC}^{*}$ 中. 證明的關鍵是用一個遞歸函數對計算所需信息進行編碼, 即把數目不定的過程值壓縮成兩個值, 隨後再解碼, 從而可以繞過規則 II 的使用, 直接定義這個函數. 問題是, 我們一般用於編碼的指數函數和素因數分解, 其定義本身就用到了規則 II. 為避免循環, Gödel 巧妙地利用了中國剩餘定理. (注意, 上面已經證明了 $\text{rem}$ 屬於 $\text{REC}^{*}$)

引理: 由中國剩餘定理可知, 對給定的 $a_1,\cdots,a_k\in\mathbb{N}$, 一定存在 $n,m\in\mathbb{N}$, 且 $n\leq m$, 滿足 $\text{rem}(1+in,m)=a_i$, 其中 $i=1,\cdots,k$. (令 $b=\max\lbrace a_1,\cdots,a_k,k\rbrace$, 並取 $n=b!$, 則 $1+n,\cdots,1+kn$ 兩兩互素)

設 $k+1$ 元函數 $f$ 滿足 $$\begin{align*} &f(n_1,\cdots,n_k,0) = g(n_1,\cdots,n_k), \\ &f(n_1,\cdots,n_k,n+1) = h(n_1,\cdots,n_k,n,f(n_1,\cdots,n_k,n)) \end{align*}$$ 其中 $g,h\in \text{REC}^{*}$. 下面我們把 $n_1,\cdots,n_k$ 簡記為 $\alpha$.
分別作 $k+2$ 元函數 $F_1$, $k+3$ 元函數 $F_2$ 和 $k+3$ 元函數 $F_3$ 如下: $$\begin{align*} &F_1(\alpha,x,y) = C_{=}(\text{rem}(1+y,x),g(\alpha)), \\ &F_2(\alpha,x,y,i) = C_{=}(\text{rem}(1+(i+2)y,x),h(\alpha,i,\text{rem}(1+(i+1)y,x))), \\ &F_3(\alpha,n,x,y) = F_1(\alpha,x,y)\times C_{\leq}(n,\mu i\left[F_2(\alpha,x,y,i)\times C_{\leq}(i,n)=0\right]). \end{align*}$$ $F_3$ 的定義使用了 $\mu$ 算子, 方括號內乘上因子 $C_{\leq}(i,n)$ 是為了確保根存在條件, 從而使 $F_3$ 是一個全函數. 容易驗證 $$F_3(\alpha,n,x,y)=1\enspace\Leftrightarrow\enspace\text{rem}(1+(i+1)y,x)=f(\alpha,i),\enspace i=0,\cdots,n$$
用 $F_3$ 作一個 $k+2$ 元函數 $F_4$: $$F_4(\alpha,n,x)=C_{\leq}(\mu y\left[\text{sg}(F_3(a,n,x,y)+C_{\leq}(x+1,y))=1\right],x)$$ 同樣, 方括號內加上 $C_{\leq}(x+1,y))$ 是為了確保根存在條件. 容易驗證 $$F_4(\alpha,n,x)=1\enspace\Leftrightarrow\enspace\exists y\leq x\enspace\text{s.t.}\enspace F_3(\alpha,n,x,y)=1$$
再用 $F_4$ 作一個 $k+1$ 元函數 $F_5$: $$F_5(\alpha,n)=\mu x\left[F_4(\alpha,n,x)=1\right]$$ 給定 $\alpha$ 和 $n$, 令引理中的 $a_1,\cdots,a_k$ 為 $f(a,0),\cdots,f(a,n)$ 這 $n+1$ 個自然數, 則由引理知, 一定存在自然數 $x$ 和 $y\leq x$, 滿足 $\text{rem}(1+(i+1)y,x)=f(\alpha,i)$, $i=0,\cdots,n$. 因此, 給定 $\alpha$ 和 $n$, 一定存在 $x$ 使得 $F_4(\alpha,n,x)=1$, 故 $F_5$ 是定義好的全函數, 且 $F_5\in\text{REC}^{*}$.

據 $F_5$ 的定義式向上回推, 可知存在 $y\leq F_5(\alpha,n)$ 使 $F_3(\alpha,n,F_5(\alpha,n),y)=1$. 因此可以作出 $k+1$ 元全函數 $F_6\in\text{REC}^{*}$: $$F_6(\alpha,n)=\mu y\left[F_3(\alpha,n,F_5(\alpha,n),y)=1\right]$$ 進而有 $$\text{rem}(1+(i+1)F_6(\alpha,n),F_5(\alpha,n))=f(\alpha,i),\enspace i=0,\cdots,n$$ 特別地取 $i=n$, 則有 $$f(\alpha,n)=\text{rem}(1+(n+1)F_6(\alpha,n),F_5(\alpha,n))$$ 這表明 $f\in\text{REC}^{*}$. $\square$

該證明的核心是壓縮變量個數, 雖然本質上是構造性的, 但從計算的角度看, 實在是繞了一個大圈子, 實際計算中當然不會這麼做. 證明過程中出現形式極為複雜的定義式, 其實是表述對某些變量相等或大小關係, 以及邏輯依賴性的條件約束. 這一部分的構造性似乎更接近於編程思維.

這樣我們就證明了 $\text{REC}\subseteq\text{REC}^{*}$, 從而任意遞歸函數都是可表示函數. 一個明顯的推論是, 任意遞歸關係在 $K_N$ 中可表示.

對形式算術的遞歸分析

Gödel 配數

對一種人工的形式語言, 我們一般要求它具有唯一讀法, 即從字母表中任取字母構成有限符號串, 我們要有辦法判斷它是項, 是公式, 還是既非項亦非公式, 如果是項或公式, 則要進一步明確它在哪一層次, 這些應當是唯一確定的. 可以證明, $K_N$ 具有唯一讀法, 具體證明略過.

有了唯一讀法, 我們就可以對 $K_N$ 這種形式語言(有限符號串)進行編碼(配數), 使 $K_N$ 算術化, 以便之後讓 $K_N$ 從內部 “談論自身”. 配數的方法有很多種, 下面是其中一種.

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

$$\begin{array}{c|cc} u & ' & + & \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)=2^{\text{g}(u_0)}\thinspace 3^{\text{g}(u_1)}\cdots\thinspace p_k^{\text{g}(u_k)}$$

其中 $p_k$ 是第 $k$ 個素數. 字母串的 Gödel 數與字母的 Gödel 數不會相同, 前者是偶數, 後者是奇數; 由自然數的唯一分解性, 不同字母串的 Gödel 數也不會相同.

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

$$\text{g}(s_0,\cdots,s_n)=2^{\text{g}(s_0)}\thinspace 3^{\text{g}(s_1)}\cdots\thinspace p_n^{\text{g}(s_n)}$$

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

重要的遞歸函數

上文已表明, 二元關係 $\text{Divi}$ 和一元關係 $\text{Prm}$ 都是遞歸關係, 函數 $p$ 是遞歸函數. 本節再引入一些有用的遞歸函數, 為下節對 $K_N$ 遞歸性質的研究做準備.

---

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

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

因為

$$(n_1)_{n_2}=\mu x\left[\text{sg}(n_1)\times\overline{\text{sg}}(\text{rem}(p_{n_2}^{x+1},n_1))=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}(C_{\text{Prm}}(x)\times C_{\text{Divi}}(x,n))$$

二元並接函數 $*$ 定義為

$$n_1 * n_2 = n_1\times\prod_{x<\text{lh}(n_2)}p_{\text{lh}(n_1)+x}^{(n_2)_x}$$

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

$$n_1 * n_2 = 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_1$ 和 $n_2$ 分別是字母串 $s_0$ 和 $s_1$ 的 Gödel 數, 那麼 $n_1 * n_2$ 就是並接 $s_0$ 和 $s_1$ 得到的字母串 $s_0\thinspace s_1$ 的 Gödel 數. 由 $(n_1)_{n_2}$ 和 $\text{lh}$ 的定義知, 函數 $*$ 也是遞歸的.

---

由 $k$ 元函數 $g$ 和 $k+2$ 元函數 $h$ 使用規則 II 生成 $k+1$ 元函數 $f$ 時, $f$ 在點 $(\alpha,n+1)$ 的值依賴於 $f$ 在點 $(\alpha,n)$ 的值 ($\alpha$ 表示 $n_1,\cdots,n_k$ ). 而在分析 $K_N$ 的性質時, 常遇到另一種函數, 它在點 $(\alpha,n+1)$ 的值依賴於 $(\alpha,0)$, $\cdots$, $(\alpha,n)$ 這些點的值, 對於這一類函數有如下結論.

設 $k+2$ 元函數 $h$ 是遞歸的, 且 $k+1$ 元函數 $f$ 滿足 “過程值遞歸條件”:

$$f(n_1,\cdots,n_k,n_{k+1})=h(n_1,\cdots,n_k,n_{k+1},f^{\sharp}(n_1,\cdots,n_k,n_{k+1}))$$

其中

$$f^{\sharp}(n_1,\cdots,n_k,n_{k+1})=\prod_{x<n_{k+1}}p_x^{f(n_1,\cdots,n_k,x)}$$

那麼 $f$ 也是遞歸函數.

證明: 我們有

$$f^{\sharp}(\alpha,n_{k+1})=\begin{cases} 2^{f(\alpha,0)}\cdots\thinspace p_{n_{k+1}-1}^{f(\alpha,n_{k+1}-1)}, &n_{k+1}>0, \\ 1, &n_{k+1}=0 \end{cases}$$

要證明 $f$ 是遞歸的, 只需證明 $f^{\sharp}$ 是遞歸的. 事實上,

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

根據規則 II, $f^{\sharp}$ 是遞歸的. $\square$

特別地, 設 $h$ 是二元遞歸函數, 一元函數 $f$ 滿足過程值遞歸條件:

$$f(n)=h(n,f^{\sharp}(n))$$

其中

$$f^{\sharp}(n)=2^{f(0)}\thinspace 3^{f(1)}\cdots\thinspace p_{n-1}^{f(n-1)}$$

則 $f$ 也是遞歸函數.

顯然, 當 $x<n_{k+1}$ 時, $f(\alpha,x)=(f^{\sharp}(\alpha,n_{k+1}))_x$. $f(\alpha,x)$ 關於 $f^{\sharp}(\alpha,n_{k+1})$ 的表達式是遞歸的, 這給出了在遞推關係式中引用已有項的合法性.

形式算術的一些遞歸性質

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

1. $\text{VS}=\left\lbrace 2^{15+2k}:k\geq 1\right\rbrace$, $\text{VS}$ 即所有個體變元的 Gödel 數構成的集;
2. $\text{TM}$: 所有 $K_N$ 的項的 Gödel 數構成的集;
3. $\text{YF}$: 所有 $K_N$ 的原子公式的 Gödel 數構成的集;
4. $\text{FM}$: 所有 $K_N$ 的公式的 Gödel 數構成的集.

證明:

1. $\text{VS}$ 的特徵函數是遞歸的:

$$C_{\text{VS}}(n) = \sum_{k<n}\left(C_{\geq}(k,1)\times C_{=}\left(n,2^{15+2k}\right)\right)$$

2. 任給一項, 必屬於這幾種可能形式: $\overline{0}$, $x_i$, $'t$, $+t_1t_2$, $\times t_1t_2$ (採用前置式寫法), 據此給出 $C_{\text{TM}}$ 滿足的關係式:

$$\begin{align*} C_{\text{TM}}(n) =& C_{=}\left(n,2^{15}\right)+C_{\text{VS}}(n)+\sum_{x<n}\left(C_{=}\left(n,2^1 * x\right)\times C_{\text{TM}}(x)\right) \\ &+ \sum_{x<n}\sum_{y<n}\left(\left(C_{=}\left(n,2^3*x*y\right)+C_{=}\left(n,2^5*x*y\right)\right)\times C_{\text{TM}}(x)\times C_{\text{TM}}(y)\right) \end{align*}$$

把上式右邊出現的所有 $C_{\text{TM}}(x)$ 和 $C_{\text{TM}}(y)$ 分別換成上一節定義的 $(C_{\text{TM}}^{\sharp}(n))_x$ 和 $(C_{\text{TM}}^{\sharp}(n))_y$, 即得 $C_{\text{TM}}$ 滿足的過程值遞歸條件, 所以 $C_{\text{TM}}$ 是遞歸函數.
3. 原子公式的結構只有 $\approx t_1t_2$ 這一種形式, 由此得到:

$$C_{\text{YF}}(n)=\sum_{x<n}\sum_{y<n}C_{\text{TM}}(x)\times C_{\text{TM}}(y)\times C_{=}\left(n,2^{13}*x*y\right)$$

4. $K_N$ 的公式除原子公式外, 便具有 $\neg q$, $q\to r$, $\forall x_i\thinspace q$ 這三種形式, 所以 $C_{\text{FM}}$ 滿足:

$$\begin{align*} C_{\text{FM}}(n) =& C_{\text{YF}}(n)+\sum_{x<n}C_{\text{FM}}(x)\times C_{=}\left(n,2^7*x\right) \\ &+ \sum_{x<n}\sum_{y<n}C_{\text{FM}}(x)\times C_{\text{FM}}(y)\times C_{=}\left(n,2^9*x*y\right) \\ &+ \sum_{x<n}\sum_{y<n}C_{\text{VS}}(x)\times C_{\text{FM}}(y)\times C_{=}\left(n,2^{11}*x*y\right) \end{align*}$$

同樣把上式右邊的 $C_{\text{FM}}(x)$ 和 $C_{\text{FM}}(y)$ 分別換成 $(C_{\text{FM}}^{\sharp}(n))_x$ 和 $(C_{\text{FM}}^{\sharp}(n))_y$, 即得 $C_{\text{FM}}$ 滿足的過程值遞歸條件, 所以 $C_{\text{FM}}$ 是遞歸函數. $\square$

---

分別對 $i=1,\cdots,5$ 把所有 $(K_i)$ 型公理的 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)$ 或公式 $p(x_i)$ 中, 用 Gödel 數為 $n_2$ 的項 $t$ 去替換 Gödel 數為 $n_1$ 的變元 $x_i$ 的所有自由出現, 所得結果 $u(t)$ 或 $p(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}$ $\Leftrightarrow$ $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)$ 或公式 $p(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}(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}(p(t)), &\text{if}\enspace n_1=\text{g}(x_i),\thinspace n_2=\text{g}(t),\thinspace n_3=\text{g}(p(x_i)); \\ (p_{n_2 n_3})^{n_2^2 n_3^2},&\text{otherwise}. \end{cases}$$

其中, 符號 $\text{g}$ 表示 Gödel 配數.

最後, 要斷定 $\text{LA}_4$ 和 $\text{LA}_5$ 的遞歸性, 還需要下面的結論.
以下關係是遞歸關係:

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}\enspace\Leftrightarrow\enspace 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{LA}_4$ 是所有形如 $\to\forall x_i\thinspace p(x_i)\thinspace p(t)$ (使用前置寫法, 其中 $t$ 對 $p$ 中 $x_i$ 自由) 的公式的 Gödel 數構成的集. 所以有 $$\begin{align*} n\in\text{LA}_4\enspace\Leftrightarrow\enspace&\exists x<n\thinspace\exists y<n\thinspace\exists z<n\big(x\in\text{VS}\wedge y\in\text{TM}\wedge z\in\text{FM}\wedge \\ &(x,y,z)\in\text{FRT}\wedge n=2^9*2^{11}*x*z*\text{Sub}(x,y,z)\big) \end{align*}$$

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

$\text{LA}_5$ 是所有形如 $\to\forall x_i\to p\thinspace q\to p\thinspace\forall x_i q$ (其中 $x_i$ 不在 $p$ 中自由出現) 的公式的 Gödel 數集. 所以 $$\begin{align*} n\in\text{LA}_5\enspace\Leftrightarrow\enspace&\exists x<n\thinspace\exists y<n\thinspace\exists z<n\big(x\in\text{VS}\wedge y\in\text{FM}\wedge z\in\text{FM}\wedge \\ &n=2^{9}*2^{11}*x*2^{9}*y*z*2^{9}*y*2^{11}*x*z\wedge (x,y)\not\in\text{FR}\big) \end{align*}$$

由 $\text{FR}$ 的遞歸性可得 $\text{LA}_5$ 的遞歸性.

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

---

令 $\text{EA}_i$ 為 $(Ei)$ 型等詞公理 Gödel 數構成的集, $\text{NA}_i$ 為 $(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 數構成的集是遞歸集.

---

以下關係和集是遞歸的:

1. $\text{MP}=\lbrace (n_1,n_2,n_3):n_1=\text{g}(p),n_2=\text{g}(p\to q),n_3=\text{g}(q)\rbrace$;
2. $\text{GEN}=\lbrace (n_1,n_2):n_1=\text{g}(p),n_2=\text{g}(\forall x_i\thinspace p)\rbrace$;
3. $\text{PF}=\lbrace n:n$ 是從 $\mathcal{N}$ 的證明的 Gödel 數 $\rbrace$;
4. $\text{PRF}=\lbrace (n_1,n_2):n_1=g(p),n_2$ 是 $p$ 從 $\mathcal{N}$ 的證明的 Gödel 數 $\rbrace$.

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

一元函數 $\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 * \text{g}(\overline{n}) = 2^1 * \text{Num}(n) \end{align*}$$

至此, 證明 Gödel 不完備性定理的準備工作已告完成.

可表示函數的遞歸性*

此前已經證明了 $\text{REC}\subseteq\text{REP}$, 現在順帶證明 $\text{REP}\subseteq\text{REC}$, 即所有在 $K_N$ 中可表示的函數都是遞歸函數.

設 $k$ 元函數 $f$ 用公式 $p(x_1,\cdots,x_k,y)$ 可表示, 其中 $y$ 是不同於 $x_1,\cdots,x_k$ 的個體變元. 把 $p(x_1,\cdots,x_k,y)$ 的 Gödel 數記為 $\alpha_0$:

$$\alpha_0=\text{g}(p(x_1,\cdots,x_k,y))$$

給定 $f$, 且取定用以表示它的公式 $p$ 之後, $\alpha_0$ 就是定數. 現用公式 $p$ 作出一個 $k+2$ 元關係 $W_p$:

$$W_p=\lbrace (n_1,\cdots,n_{k+2}):n_{k+2} \text{ 是 } p(\overline{n_1},\cdots,\overline{n_{k+1}}) \text{ 從 } \mathcal{N} \text{ 的證明的 Gödel 數 } \rbrace$$

把 $p(\overline{n_1},x_2,\cdots,x_k,y)$, $p(\overline{n_1},\overline{n_2},x_3,\cdots,x_k,y)$, $\cdots$, $p(\overline{n_1},\cdots,\overline{n_{k+1}})$ 的 Gödel 數分別記為 $\alpha_1(n_1)$, $\alpha_2(n_1,n_2)$, $\cdots$, $\alpha_{k+1}(n_1,\cdots,n_{k+1})$. 這是一串遞歸函數:

$$\begin{align*} &\alpha_1(n_1) = \text{Sub}(2^{15+2},\text{Num}(n_1),\alpha_0), \\ &\alpha_2(n_1,n_2) = \text{Sub}(2^{15+4},\text{Num}(n_2),\alpha_1(n_1)), \\ &\cdots , \\ &\alpha_{k+1}(n_1,\cdots,n_{k+1}) = \text{Sub}(2^{15+2(k+1)},\text{Num}(n_{k+1}),\alpha_k(n_1,\cdots,n_k)) \end{align*}$$

所以由 $W_p$ 的定義即可知 $W_p$ 是遞歸的:

$$C_{W_p}(n_1,\cdots,n_{k+2})=C_{\text{PRF}}\left(\alpha_{k+1}(n_1,\cdots,n_{k+1}),n_{k+2}\right)$$

因為 $f$ 可由公式 $p(x_1,\cdots,x_k,y)$ 表示, 所以

$$\mathcal{N}\vdash p\left(\overline{n_1},\cdots,\overline{n_k},\thinspace \overline{f(n_1,\cdots,n_k)}\right)$$

把 $p\left(\overline{n_1},\cdots,\overline{n_k},\thinspace \overline{f(n_1,\cdots,n_k)}\right)$ 從 $\mathcal{N}$ 的一個證明的 Gödel 數記為 $m$, 則有

$$(n_1,\cdots,n_k,f(n_1,\cdots,n_k),m)\in W_p$$

這說明, 對任意的 $n_1,\cdots,n_k$, 一定存在 $x\in\mathbb{N}$ 使

$$(n_1,\cdots,n_k,(x)_0,(x)_1)\in W_p$$

例如令 $x=2^{f(n_1,\cdots,n_k)}\thinspace 3^m$ 即可. 所以如下定義的 $k$ 元函數 $x^{*}$ 是遞歸全函數:

$$x^{*}(n_1,\cdots,n_k)=\mu x\left[C_{W_p}(n_1,\cdots,n_k,(x)_0,(x)_1)=1\right]$$

於是我們有

$$\mathcal{N}\vdash p\left(\overline{n_1},\cdots,\overline{n_k},\thinspace \overline{(x^{*}(n_1,\cdots,n_k))_0}\right)\tag{1}$$

假設 $f(n_1,\cdots,n_k)\not=(x^{*}(n_1,\cdots,n_k))_0$, 則會得到

$$\mathcal{N}\vdash\neg p\left(\overline{n_1},\cdots,\overline{n_k},\thinspace \overline{(x^{*}(n_1,\cdots,n_k))_0}\right)\tag{2}$$

與 $(1)$ 式矛盾. 如果 $\mathcal{N}$ 是無矛盾的, 就必然有

$$f(n_1,\cdots,n_k)=(x^{*}(n_1,\cdots,n_k))_0$$

是遞歸函數. $\square$

從而在 $\mathcal{N}$ 無矛盾的前提下, 我們證明了可表示函數必是遞歸函數. 結合上面的結論就有 $\text{REC}=\text{REP}$, 遞歸性與在 $K_N$ 中的可表示性是一回事.

在這個證明中, 我們利用了 $\text{PRF}$ ($\text{PF}$) 的遞歸性, 而 $\text{PRF}$ 的遞歸性僅僅依賴於公理集的遞歸性, 所以如果對 $\mathcal{N}$ 進行無矛盾擴張 $\mathcal{N}^{*}$, 但保持 $\mathcal{N}^{*}$ 中公理的 Gödel 數集的遞歸性, 則對擴張後系統中的可表示函數, 上述結論仍然成立.

部分遞歸函數*

從程序語言的角度看, 原始遞歸函數相當於進行有界的循環, 即形如 “從 $i=1$ 到 $n$ 執行…” 的一系列預先確定的運算; 而 $\mu$ 算子使得程序可以進行無界的循環, 即從 $i=1$ 開始逐個檢驗, 直到搜索得最小根, 一個函數滿足根存在性條件, 就意味著循環必定有終點 (停機), 這樣的函數就是一般遞歸函數. 進而, 如果去除根存在性條件, 那麼這種循環就有可能不會終止.

上文已經提到, 部分遞歸函數是在使用規則 III 時去掉根存在性條件所得, 確切地說, 設 $k+1$ 元部分函數 $g$, 對其使用 $\mu$ 算子得到函數 $f$:

$$f(\alpha)=\mu x\left[\forall z\leq x\thinspace (g(\alpha,z)\downarrow)\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\thinspace (g(\alpha,z)\downarrow)$ 是因為, $g(\alpha,x)$ 可以是部分函數, 有可能在最小根 $x_0$ 出現前, 就在某個 $z_0<x_0$ 處無定義, 假如跳過 $z_0$, 那麼即便找到了 $x_0$ 這個根, 我們也不能斷言 $x_0$ 是最小的, 因為我們不能能行地知道 $g(\alpha,z_0)$ 是發散的. 所以我們寧可達不到真正的根, 也不跳過發散點.

形成部分遞歸函數的這條規則, 可以作用在部分函數上, 也可以產生部分函數. 事實上, Turing 給出的可計算性概念面向的是 $\mathbb{N}$ 上的部分函數, 而不僅僅是全函數: 一個可計算函數可能並非在所有輸入值上都有定義, 對某些輸入, 一個計算程序可能會一直運行, 永不停止. 正是由於這個部分性特徵, Turing 的計算概念能避開 Gödel 的對角化難題 (對原始遞歸函數的任何枚舉總可以通過對角化增添新的可計算函數, 參見上文), 達成對可計算函數的完全的枚舉. 簡單來說, 假定我們枚舉所有的部分遞歸函數: $f_0, f_1, \cdots$, 並定義對角函數 $F:\mathbb{N}\to\mathbb{N}$ 為 $F(n)=f_n(n)+1$, 則 $F$ 可以與列表中的某個 $f_{k}$ 相同, 因為 $f_k(k)$ 無定義.

Church 論題: 算法可計算函數 = 遞歸函數.
這是一個經驗事實, 但還未發現反例. 上文已經證明 $\text{FM}$ 和 $\text{PF}$ 是遞歸集, 所以按 Church 論題, 存在算法能用來確定任給的 $n\in\mathbb{N}$ 是否屬於 $\text{FM}$ 或 $\text{PF}$, 即存在算法能確定任意字母串是不是 $K_N$ 的公式, 以及任給的有限公式序列是不是從 $\mathcal{N}$ 的一個證明.

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