數理邏輯筆記 No.3
形式算術
等詞
在上一篇定義的謂詞演算基礎上, 我們引入一個特殊的二元謂詞: 等詞 $R^2_1$, 這個謂詞用以形式化表達我們心目中的 “相等” 概念, 形式算術 $K_N$ 即是一種帶等詞的謂詞演算. 下面我們把 $R^2_1$ 簡記為 “$\approx$”.
在帶有等詞的謂詞演算 $K$ 中, 以下三種形式的公式叫做等詞公理:
$(E1)$ $t\approx t$;
$(E2)$ $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)$ $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))$.
其中 $t_1,\cdots,t_n$ 是任意的項, $k=1,\cdots,n$. 記 $E=\left\{E1,E2,E3\right\}$.
需要注意的是, 這些等詞公理不是有效式, 即它並非在 $K$ 的任何解釋域中恆真. 但當 “$\approx$” 在解釋域中解釋為 “相等” 時, 該解釋域一定是 $E$ 的模型.
容易證明:
- $E\vdash t\approx t$; (自反性)
- $E\vdash t\approx u\to u\approx t$; (對稱性)
- $E\vdash t\approx u\to(u\approx v\to t\approx v)$. (傳遞性)
由此可知, 等詞 “$\approx$” 在公理集 $E$ 的模型中不一定解釋為 “相等”, 但它所解釋的二元關係一定是等價關係.
形式算術 $K_N$
形式算術 $K_N$ 指一種特殊的帶等詞的謂詞演算, 它有一個個體常元 $c_1$, 三個函數詞: $f^1_1$, $f^2_1$, $f^2_2$, 和一個二元謂詞 $\approx$.
$K_N$ 有一個自然的解釋域: 自然數集 $\mathbb{N}=\left\{0,1,2,\cdots\right\}$. 在 $\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$ 中所有等詞公理及如下形式的公式都叫做算術公理:
$(N1)$ $t’\not\approx \overline{0}$;
$(N2)$ $t_1’\approx t_2’\to t_1\approx t_2$;
$(N3)$ $t+\overline{0}\approx t$;
$(N4)$ $t_1+t_2’\approx (t_1+t_2)’$;
$(N5)$ $t\times\overline{0}\approx \overline{0}$;
$(N6)$ $t_1\times t_2’\approx t_1\times t_2+t_1$;
$(N7)$ $p(\overline{0})\to(\forall x(p(x)\to p(x’))\to\forall x\thinspace p(x))$
其中 $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}$,
- $f(n_1,\cdots,n_k)=m$ $\Rightarrow$ $\mathcal{N}\vdash p(\overline{n_1},\cdots,\overline{n_k},\overline{m})$;
- $f(n_1,\cdots,n_k)\not=m$ $\Rightarrow$ $\mathcal{N}\vdash\neg p(\overline{n_1},\cdots,\overline{n_k},\overline{m})$;
- $\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$ 元投影函數 $p^k_i$:
$$p^k_i(n_1,\cdots,n_k)=n_i,\quad (i=1,\cdots,k)$$
則函數 $+$, $\times$, $p^k_i$ 在 $K_N$ 中是可表示的:
- 二元和函數 $+$ 由公式 $x_1+x_2\approx y$ 表示;
- 二元乘積函數 $\times$ 由公式 $x_1\times x_2\approx y$ 表示;
- $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)$ 中出現的變元.
關係
$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$ $\Rightarrow$ $\mathcal{N}\vdash p(\overline{n_1},\cdots,\overline{n_k})$;
- $(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\{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)\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\{x:g(n_1,\cdots,n_k,x)=0\right\}$$
即 $f(n_1,\cdots,n_k)$ 是使 $g(n_1,\cdots,n_k,x)$ 的 $x$ 的最小值. 我們把 $f$ 說成是由 $g$ 使用最小數算子或 $\mu$ 算子得來的, 記作
$$f(n_1,\cdots,n_k)=\mu\thinspace 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})$ 中出現的變元. 這個公式的含義在直觀上是很明顯的.
遞歸函數
遞歸函數是一類重要的數論函數, 也是遞歸論的研究對象, 直觀來看, 遞歸函數即是可計算函數之概念的精確化 (因此, 遞歸論也叫可計算性理論).
一般遞歸函數
首先定義三種基本函數:
- 一元零函數 $z$, $z(n)=0$;
- 一元後繼函數 $s$, $s(n)=n+1$;
- $k$ 元投影函數 $p^k_i$, $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\thinspace x\left[g(n_1,\cdots,n_k,x)=0\right]$$
若去掉規則 III, 只允許使用規則 I, II, 則定義的函數叫做原始遞歸函數. 原始遞歸算術 (Primitive Recursive Arithmetic, PRA) 是 Hilbert 有窮主義數學的形式化, 其中只包含原始遞歸函數. 然而, 這個形式系統已經足夠強, 可以從中推出 Gödel 不完全性定理.
若去掉規則 III 中根存在性條件的限制, 則定義的函數叫做部分遞歸函數 (或遞歸偏函數). 部分遞歸函數不一定處處有定義, 所以不一定是全函數.
下面列舉一些常用的(原始)遞歸函數:
- $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*}
$$ - 二元和函數 $+$
$$
\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*}
$$ - 二元乘積函數 $\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*}
$$ - 前鄰函數 $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*}
$$ - 截差函數 $\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*}
$$ - 一元函數 $\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*}
$$ - 一元函數 $\overline{\text{sg}}$, $\overline{\text{sg}(n)}=1\dot{-}\text{sg}(n)$.
插入一個命題: 由 $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))$$
該命題可由於 “增元” 或 “減元”.
- 絕對差 $\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)$$ - $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*}
$$ - 指數函數 $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*}
$$ - 餘數函數 $\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*}
$$ - 設 $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*}
$$ - 設 $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$. ) - 設 $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{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$ 元遞歸關係.
設 $R$ 是 $k+1$ 元遞歸關係, 作一 $k$ 元關係:
$$Q=\left\{(n_1,\cdots,n_k):\exists x<n_k\enspace \text{s.t.}\enspace (n_1,\cdots,n_k,x)\in R\right\}$$
則 $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\{a\right\}$, 有限集 $\left\{a_1,\cdots,a_n\right\}$ 都是遞歸集. 因為 $C_{\mathbb{N}}=1$, $C_{\varnothing}=0$, $C_{\left\{a\right\}}=C_{=}(n,a)$, $\left\{a_1,\cdots,a_n\right\}=\bigcup_{i=1}^n \left\{a_i\right\}$.
定義二元關係 $\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\thinspace 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}^{*}$.
- $\text{REP}$: 在 $K_N$ 中可表示的函數全體構成的集;
- $\text{REC}$: 遞歸函數全體構成的集;
- $\text{REC}^{*}$: $+$, $\times$, $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}^{*}$. 因為:
- $s(n)=n+C_{\leq}(n,n)=p^1_1(n)+C_{\leq}(p^1_1(n),p^1_1(n))$;
- $z(n)=C_{\leq}(n+1,n)=C_{\leq}(s(n),p^1_1(n))$;
- $\text{sg}(n)=C_{\leq}(1,n)=C_{\leq}(s(z(n)),p^1_1(n))$;
- $\overline{\text{sg}}(n)=C_{\leq}(p^1_1(n),s(z(n)))$;
- $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))$;
- $n_1\dot{-}n_2=\mu\thinspace x\left[\overline{\text{sg}}(C_{\leq}(n_1,n_2+x))=0\right]$;
- $\text{rem}(n_1,n_2)=\text{sg}(n_1)\times(n_2\dot{-}(n_1\times(\mu\thinspace 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}^{*}$ 中.
證明
引理: 由中國剩餘定理可知, 對給定的 $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$. ($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\thinspace 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\thinspace 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\thinspace 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\thinspace 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}^{*}$.
這個證明實質上是構造性的, 它給出了不使用規則 II, 由 $g$ 和 $h$ 直接構造 $f$ 的表達式的具體方法, 但這個構造沒有給出明確的計算方法, 只是對計算所需的信息進行編碼. 所以從計算的角度看, 規則 II 仍是必不可少的. 過程中出現形式極為複雜的定義式, 其實是表述對某些變量相等或大小關係, 以及邏輯依賴性的條件約束.
這樣我們就證明了 $\text{REC}\subseteq\text{REC}^{*}$, 從而任意遞歸函數都是可表示函數. 一個明顯的推論是, 任意遞歸關係在 $K_N$ 中可表示.
對 $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\thinspace 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’(n_1,\cdots,n_k,n_{k+1}))$$
其中
$$f’(n_1,\cdots,n_k,n_{k+1})=\prod_{x<n_{k+1}}p_x^{f(n_1,\cdots,n_k,x)}$$
那麼 $f$ 也是遞歸函數.
證明: 我們有
$$
f’(\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’$ 是遞歸的. 事實上,
$$
\begin{align*}
&f’(\alpha,0) = 1, \\
&f’(\alpha,n+1) = f’(\alpha,n)\times p_n^{f(\alpha,n)}=f’(\alpha,n)\times p_n^{h(\alpha,n,f’(\alpha,n))}
\end{align*}
$$
根據規則 II, $f’$ 是遞歸的.
特別地, 設 $h$ 是二元遞歸函數, 一元函數 $f$ 滿足過程值遞歸條件:
$$f(n)=h(n,f’(n))$$
其中
$$f’(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’(\alpha,n_{k+1}))_x$. $f(\alpha,x)$ 關於 $f’(\alpha,n_{k+1})$ 的表達式是遞歸的, 這給出了在遞推關係式中引用已有項的合法性.
$K_N$ 的一些遞歸性質
$\mathbb{N}$ 的以下子集是遞歸集:
- $\text{VS}=\left\{2^{15+2k}:k\geq 1\right\}$, $\text{VS}$ 即所有個體變元的 Gödel 數構成的集;
- $\text{TM}$: 所有 $K_N$ 的項的 Gödel 數構成的集;
- $\text{YF}$: 所有 $K_N$ 的原子公式的 Gödel 數構成的集;
- $\text{FM}$: 所有 $K_N$ 的公式的 Gödel 數構成的集.
證明:
- $\text{VS}$ 的特徵函數是遞歸的:
$$C_{\text{VS}}(n) = \sum_{k<n}\left(C_{\geq}(k,1)\times C_{=}(n,2^{15+2k})\right)$$ - 任給一項, 必屬於這幾種可能形式: $\overline{0}$, $x_i$, $’t$, $+t_1t_2$, $\times t_1t_2$ (採用前置式寫法), 據此給出 $C_{\text{TM}}$ 滿足的關係式:
$$
\begin{align*}
C_{\text{TM}}(n) =& C_{=}(n,2^{15})+C_{\text{VS}}(n)+\sum_{x<n}(C_{=}(n,2^1 * x)\times C_{\text{TM}}(x)) \\
&+ \sum_{x<n}\sum_{y<n}\left((C_{=}(n,2^3*x*y)+C_{=}(n,2^5*x*y))\times C_{\text{TM}}(x)\times C_{\text{TM}}(y)\right)
\end{align*}
$$
把上式右邊出現的所有 $C_{\text{TM}}(x)$ 和 $C_{\text{TM}}(y)$ 分別換成上一節定義的 $(C_{\text{TM}}’(n))_x$ 和 $(C_{\text{TM}}’(n))_y$, 即得 $C_{\text{TM}}$ 滿足的過程值遞歸條件, 所以 $C_{\text{TM}}$ 是遞歸函數. - 原子公式的結構只有 $\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_{=}(n,2^{13}*x*y)$$ - $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_{=}(n,2^7*x) \\
&+ \sum_{x<n}\sum_{y<n}C_{\text{FM}}(x)\times C_{\text{FM}}(y))\times C_{=}(n,2^9*x*y) \\
&+ \sum_{x<n}\sum_{y<n}C_{\text{VS}}(x)\times C_{\text{FM}}(y))\times C_{=}(n,2^{11}*x*y)
\end{align*}
$$
同樣把上式右邊的 $C_{\text{FM}}(x)$ 和 $C_{\text{FM}}(y)$ 分別換成 $(C_{\text{FM}}’(n))_x$ 和 $(C_{\text{FM}}’(n))_y$, 即得 $C_{\text{FM}}$ 滿足的過程值遞歸條件, 所以 $C_{\text{FM}}$ 是遞歸函數.
分別對 $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\thinspace x\left[C_{\text{SBS}}(n_1,n_2,2^{n_3}\thinspace 3^{x})+C_{\leq}((p_{n_2 n_3})^{n_2^2 n_3^2},x)=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$ 的遞歸性, 還需要下面的結論.
以下關係是遞歸關係:
- $\text{FR}=\{(n_1,n_2):n_1$ 變元在 $n_2$ 項或 $n_2$ 公式中自由出現 $\}$
- $\text{FRT}=\{(n_1,n_2,n_3):n_2$ 項對 $n_3$ 公式中的 $n_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}$$ - 分四種情形, 寫出 $C_{\text{FRT}}$ 所滿足的過程值遞歸條件, 細節略.
$\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\text{EA}_2\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}=\left\{(n_1,n_2,n_3):n_1=\text{g}(p),n_2=\text{g}(p\to q),n_3=\text{g}(q)\right\}$;
- $\text{GEN}=\left\{(n_1,n_2):n_1=\text{g}(p),n_2=\text{g}(\forall x_i\thinspace p)\right\}$;
- $\text{PF}=\{n:n$ 是從 $\mathcal{N}$ 的證明的 Gödel 數 $\}$;
- $\text{PRF}=\{(n_1,n_2):n_1=g(p),n_2$ 是 $p$ 從 $\mathcal{N}$ 的證明的 Gödel 數 $\}$.
證明略. 這裡需要注意的是, $\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=\{(n_1,\cdots,n_{k+2}):n_{k+2}$ 是 $p(\overline{n_1},\cdots,\overline{n_{k+1}})$ 從 $\mathcal{N}$ 的證明的 Gödel 數 $\}$
把 $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(\overline{n_1},\cdots,\overline{n_k},\thinspace \overline{f(n_1,\cdots,n_k)})$$
把 $p(\overline{n_1},\cdots,\overline{n_k},\thinspace \overline{f(n_1,\cdots,n_k)})$ 從 $\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\thinspace 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$$
是遞歸函數.
從而在 $\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\thinspace 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)$ 無定義.