【Under Construction】一些逻辑话题：递归论初步与哥德尔不完备定理

Posted on Edited on In ,

Abstract. 离散数学与结构作业出了一个题考察对哥德尔不完备定理的深度理解，但是他上课实在是讲得过于粗糙，于是我们被迫完整阅读一遍相关理论。参考资料是 Dirk van Dalen, Logic and Structure(Fifth Edition), Springer(2013) Chapter 8 Godel’s Theorem。

原始递归函数

考虑自然数集合。我们希望从一系列初始的函数开始，通过复合与拼接、递归构造一系列可以高速计算的数值函数。当然作为数理逻辑研究，我们必须给出准确的定义。

首先给出初始函数的定义。初始函数包含如下形式的函数：

  • 常函数 $C_m^k$，其中 $C_m^k(n_0, …, n_{k-1}) = m$；
  • 后继 $S$，其中 $S(n) = n + 1$；
  • 投影函数 $P_i^k$，其中 $P_i^k(n_0, …, n_k) = n_i$。

现在考虑一类函数 $\mathcal{F}$，我们称：

  • $\mathcal{F}$ 对复合封闭，如果 $g, h_0, …, h_{p-1}\in \mathcal{F}$，那么 $f\in \mathcal{F}$，其中 $f(\vec{n}) = g(h_0(\vec{n}), …, h_{p-1}(\vec{n}))$。

  • $\mathcal{F}$ 对原始递归封闭，如果 $g, h\in\mathcal{F}$，那么 $f\in\mathcal{F}$，其中

    $$
    \begin{cases}
    f(0, \vec{n}) = g(\vec{n}) \\
    f(m + 1, \vec{n}) = h(f(m, \vec{n}), \vec{n}, m)
    \end{cases}
    $$

定义 1.1（原始递归函数类） 原始递归函数类定义为包含初始函数、对复合和原始递归封闭的最小类。

例子 1.2. 考虑用原始递归函数定义加法，可以形象地写作

$$
\begin{cases}
x + 0 = x\\
x + (y + 1) = (x + y) + 1
\end{cases}
$$

也可以精确写作

$$
\begin{cases}
+(0, x) = P_0^1(x) \\
+(y + 1, x) = S(P_0^3(+(y, x), P_0^2(x, y), P_1^2(x, y)))
\end{cases}
$$

其他简单操作如乘法、截断减法、阶乘也都是原始递归的，如果学过 FP 那么写起来就像回家了一样。简便起见，以后我们将采用形象的写法。

至此已经可以验证一些显然的结论，如

引理 1.3. 如果 $f$ 是原始递归函数，那么

  • $g$ 也是原始递归函数，其中 $g(x_0, …, x_{n - 1}, z_0, …, z_{k - 1}) = f(x_0, …, f_{n - 1})$。
  • 将某一维代入另一维（i.e. $f(x_0, …, x_{n - 1})[x_i / x_j]$ 或者直观写作 $f(x_0, …, x_i, …, x_i, …, x_{n - 1})$）也是原始递归函数。
  • 将变量顺序循环排列得到的也是原始递归函数。

证明

只需灵活应用复合封闭和投影函数即可。

对于一个 $k$ 元关系 $A\subset \mathbb{N}^k$，定义其特征函数 $K_A : \mathbb{N}^K\rightarrow \{0, 1\}$ 为满足 $\vec{n}\in A \Leftrightarrow K_A(\vec{n}) = 1$ 的函数。

定义 1.4（原始递归关系）. 称一个关系 $R$ 是原始递归的，若其特征函数是原始递归函数。

下面诸引理和引理 1.3 的证明同样初等：

引理 1.5. 原始递归关系对于以下操作封闭：

  • 交并补、有界量词（如 $\exists y\leq C$）。
  • 原始递归替换。即 $f_0, …, f_{n-1}$ 是原始递归关系，$R$ 是原始递归关系，那么 $S(\vec{x}) = R(f_0(\vec{x}), …, f_{n - 1}(\vec{x}))$ 是原始递归关系。

证明.

Trivial.

引理 1.6. 原始递归函数对模式匹配封闭。即如果 $R_1, …, R_p$ 是两两互斥的原始递归谓词（一元关系），并且 $\forall x (R_1(x)\vee \cdots\vee R_p(x))$，那么给定原始递归函数 $g_1, …, g_p$，有

$$
f(\vec{x}) = \begin{cases}
g_1(\vec{x}) & R_1(\vec{x}) \\
\vdots \\
g_p(\vec{x}) & R_p(\vec{x})
\end{cases}
$$

亦是原始递归函数。

证明.

注意

$$
f(\vec{x}) = \sum_{i=1}^p g_i(\vec{x})K_{R_i}(\vec{x})
$$

是原始递归函数的复合。

我们定义有界最小值 $(\mu y < m) R(\vec{x}, y)$ 表示最小的满足 $R(\vec{x}, y)$ 的 $y$，如果不存在则置为 $m$。容易发现

引理 1.7. 有界最小值作用于原始递归关系得到的函数是原始递归的。

初等数论的一套基本函数都是原始递归的，此理论对于后面哥德尔不完备定理的证明（哥德尔配数部分）而言至关重要，兹简单说明：

  • 素性测试谓词

    $$
    Prime(x) \Leftrightarrow \forall y \leq x (\forall z \leq x ((yz = x)\rightarrow (y = 1\vee z = 1)))
    $$

  • 整除关系

    $$
    x | y \Leftrightarrow \exists z \leq y (xz = y)
    $$

  • 提取一个素数的指数

    $$
    \alpha(p) = (\mu y\leq x) [p^y | x \wedge \neg p^{y + 1} | x]
    $$

  • 第 $n$ 个素数

    $$
    \begin{cases}
    p(0) = 2 \\
    p(n + 1) = (\mu x \leq p(n)^{n + 2})(Prime(x) \wedge x > p(n))
    \end{cases}
    $$

    Remark. 这里用到的 $p(n)^{n + 2}$ 是一个非常宽松但不算直观的上界，只需要考虑初等数论经典证明中的

    $$
    \forall i\leq n \left(\neg p(i) | \prod_{i=0}^n p(n) + 1\right)
    $$

这些理论将被用于定义有限序列的编码，这可以被简单地形式化为（用 $\langle n_0, …, n_{k-1}\rangle$ 表示序列 $n_0, …, n_{k-1}$ 的编码）：

$$
\langle \cdot, …, \cdot \rangle : {n_0, …, n_{k - 1}} \mapsto \prod_{i=1}^k p_{i - 1}^{n_{i - 1} \color{red}{ + 1}}
$$

并且可以附加一些原始递归的函数，来对序列编码进行操作：

  • $Seq(n)$ 检验 $n$ 是否是一个编码数：

    $$
    Seq(n) := n\ne 0 \wedge\forall p \leq n \forall q\leq n ((Prime(p) \wedge Prime(q) \wedge p < q \wedge q | n) \rightarrow p | n)
    $$

  • $lth(n)$ 返回编码数对应序列的长度：

    $$
    lth(n) := (\mu x \leq n + 1) [\neg p(x) | n]
    $$

  • $(n)_i$ 为投影（取对应序列的第 $i$ 位）。只需要提取指数即可。

  • $n * m$ 为序列拼接：

    $$
    n * m := n * \prod_{i=0}^{lth(m) - 1} p_{lth(n) + i}^{(m)_i + 1}
    $$

对于一个函数，可以用值过程函数（course-of-value function）来展示其求值过程。

$$
\begin{cases}
\bar{f}(0, \vec{x}) = 1 \\
\bar{f}(y + 1, \vec{x}) = \bar{f}(y, \vec{x})p_y^{f(y, \vec{x}) + 1}
\end{cases}
$$

显然值过程函数也是原始递归的。顺带一提 course-of-value 是做函数式动态规划时的一个经典而直接的 trick。这是因为在进行原始递归时访问先前的结果，得到的还是原始递归函数，形式化地：

定理 1.8. 若 $g$ 是原始递归函数，且 $f$ 满足

$$
f(y, \vec{x}) = g(\bar{f}(y, \vec{x}), y, \vec{x})
$$

那么 $f$ 也是原始递归的。

证明.

可以发现 $\vec{f}$ 是原始递归函数，$f$ 本身无非是再经过一次复合得到的结果。

但很遗憾原始递归函数并不是一个完备的集合。

定理 1.9. 存在一个良定义的函数，它不是原始递归的。

证明.

首先，将原始递归函数编码成自然数。这一步一定是可行的，因为结构归纳地看，原始递归函数无非是复合或是原始递归的产物，只需将这两种构造看成字符串，然后编码字符串即可，解码工作也是可以进行的。

现在称编码为 $x$ 的原始递归函数为 $f_x$，那么函数 $D(x) = f_x(x) + 1$ 是良定义的。但 $D$ 不可能是原始递归的，否则假设其编码为 $n$ 即 $D = f_n$，但 $D(n) = f_n(n) + 1 \ne f_n(n)$，这导出矛盾。明所欲证。

Remark. 上述证明使用的技巧正是众所周知的对角线法。

将此定理的证明推而广之，我们知道函数 $F(x, y) := f_x(y)$ 一定也不是原始递归的。换言之，原始递归函数集合并非递归可枚举的，这个概念将在今后的章节中反复出现。

部分递归函数

我们之前谈到没有一个有效的算法能够枚举原始递归函数。现在我们用所谓的部分递归函数来扩充我们能表示的函数范围。部分函数顾名思义就是定义域并非是 $\mathbb{N}^k$ 状的向量全体，而是其中的一部分（参考所谓的 partial map / total map）。

Remark. 此处的英文术语写作 partial recursive functions，原书中已经澄清了这是一个历史遗留的不便于理解的术语，然而直接按照 partial, recursive function 翻译又过于拗口，于是还是直译成部分递归函数。

在本节中，我们将精确地描述什么是“算法”。我们使用的技巧是直接将算法视为某种抽象的机器在操作一个有限长度的向量。一个算法将有一个标号，接下来我们同时定义编码的方式和抽象机作用于向量的语义建模成的关系。

记号 2.1. 记 $\{e\}(\vec{x})\simeq y$ 若标号为 $e$ 的抽象机在 $\vec{x}$ 上运行得到结果 $y$。

某一抽象机很有可能在一个输入上是不停机的，此时称此 $\{e\}(\vec{x})$ 发散，否则称其收敛。

定义 2.2. 递归定义 $\{e\}(\vec{x})\simeq y$ 的语义如下：

  1. $\{\langle 0, n, q\rangle\}(m_0, …, m_{n-1}) \simeq q$（常函数）
  2. $\{\langle 1, n, i\rangle\}(m_0, …, m_{n-1}) \simeq m_i$（投影函数）
  3. $\{\langle 2, n, i\rangle\}(m_0, …, m_{n-1}) \simeq m_i + 1$（后继函数）
  4. $\{\langle 3, n + 4\rangle\}(p, q, r, s, m_0, …, m_{n - 1}) \simeq p$ 若 $r=s$；$\{\langle 3, n + 4\rangle\}(p, q, r, s, m_0, …, m_{n-1})\simeq q$ 若 $r\ne s$（选择函数）
  5. $\{\langle 4, n, b, c_0, …, c_{k-1}\rangle\}(m_0, …, m_{n-1})\simeq p$ 若存在 $q_0, …, q_{k-1}$ 使得 $\{c_i\}(q_i)$ 且 $\{b\}(q_1, …, q_k) \simeq p$（复合函数）
  6. $\{\langle 5, n + 2\rangle\}(p, q, m_0, …, m_{n-1})\simeq S_n^1(p, q)$（这里 $S$ 函数我们稍后说明其含义，本条类似于 Curry 化）
  7. $\{\langle 6, n + 1\rangle\}(b, m_0, …, m_{n-1})\simeq p$ 若 $\{b\}(m_0, …, m_{n-1}) \simeq p$（通用函数）

这个关系之所以被称为部分递归函数，是因为

  1. 它确实是一个函数关系（见下方引理 2.3）；
  2. 他并非定义在普遍的定义域上（存在不停机的抽象机）；
  3. 它是归纳定义的。尤其注意本条，因为使用此归纳定义的函数完成递归任务是一件高度非平凡的事情。

引理 2.3. 上述关系是函数关系，即 $\{e\}(\vec{x})\simeq y \wedge \{e\}(\vec{x})\simeq z \rightarrow y=z$。

证明.

只需施归纳于 $e$ 即可。

接下来我们可能会将此类部分函数简单地记作一个希腊字母如 $\varphi$ 等。另外对于具体地抽象机 $e$ 和输入 $\vec{x}$，我们用 $\{e\}(\vec{x})$ 来表示对应的 $y$。此外，我们区分以下称呼：

  1. 部分递归函数，指 $\{e\}$；
  2. 抽象机，指 $e$ 对应的机器；
  3. 编码，指 $e$。

定义 2.4.

  1. 若 $\varphi$ 满足 $\exists y, \varphi(\vec{x}) = y$，那么称此部分函数在 $\vec{x}$ 收敛，反之称其发散。
  2. 若一个部分函数在其定义域上（即 $\mathbb{N}^n$）均收敛，那么称其是完全的。
  3. 完全的部分递归函数称为递归函数。
  4. 一个关系是递归的若其特征函数是递归函数。

在上方的归纳定义中第五条和第七条尤其重要，巧妙应用这两个函数可以实现分支判断、递归等操作。作为例子，我们来求编码 $e$ 使得

$$
\{e\}(\vec{x}) = \begin{cases}
\{e_1\}(\vec{x}) & g_1(\vec x) = g_2(\vec x) \\
\{e_2\}(\vec{x}) & \text{otherwise}
\end{cases}
$$

答案.

首先考虑

$$
\varphi(\vec{x}) = \begin{cases}
e_1 & g_1(\vec x) = g_2(\vec x) \\
e_2 & \text{otherwise}
\end{cases}
$$

显然这就是

$$
\varphi(\vec{x}) = \{\langle 3, 4\rangle\}(e_1, e_2, g_1(\vec{x}), g_2(\vec{x}))
$$

换言之

$$
\varphi = \langle 4, n, \langle 3, 4\rangle, \langle 1, n, e_1\rangle, \langle 1, n, e_2\rangle, g_1, g_2\rangle
$$

然后注意

$$
\{e\}(\vec{x}) = \{6, n+1\}(\varphi(\vec{x}), x)
$$

也就是

$$
e = \langle 4, n, \langle 6, n + 1\rangle, \varphi, \langle 1, n, 0\rangle, …, \langle 1, n, n-1\rangle\rangle
$$

接下来的一个定理给出上述 $S_n^m$ 函数的定义，我们指出部分递归函数的 Curry 化是原始递归的。

定理 2.5（$S_n^m$ 定理）. 对于任意的 $m, n$，存在一个原始递归函数 $S_n^m$ 使得

$$
\{ S_n^m(e, x_0, …, x_{m-1})\}(x_m, …, x_{n-1}) = \{e\}(\vec{x})
$$

证明.

施归纳于 $m$。首先证明 $S_n^1$ 是原始递归函数。这是因为

$$
S_n^1(e, y) = \langle 4, (e)_1 - 1, e, \langle 0, (e)_1 - 1, y\rangle, \langle 1, (e)_1 - 1, 0\rangle, …, \langle 1, (e)_1 - 1, (e)_1 - 2\rangle \rangle
$$

上式中所有的操作都是先前已经定义的原始递归函数，因此 $S_n^1$ 确实是原始递归的。

若 $S_n^m$ 是原始递归函数，那么 $S_n^{m + 1}$ 也是原始递归函数：只需对 $S_n^m$ 应用一次上式即可。

我们先前已经定义了一个分支选择函数，现在我们还希望函数的性质能够再好一些，即可以递归。这样一来，我们便能实现绝大部分习见的算法。回忆在 Lambda 演算当中 $Y$ 组合子的性质：

$$
Y f = f (Y f)
$$

倘若能够找到一个这样的 $Y$，我们便可用相似的手法定义本套理论中的递归。事实上 $Y$ 不仅是存在的，而且是原始递归的。形式化地有下列定理：

定理 2.6（递归定理）. 存在一个原始递归函数 $rc$ 使得

$$
\{rc(e)\}(\vec{x}) = \{e\}(rc(e), x)
$$

证明.

我们定义

$$
\varphi(m, e, \vec{x}) = \{e\}(S_{n + 2}^2(m, m, e), \vec{x})
$$

此函数的编码正是

$$
\begin{aligned}
&\langle 4, (e)_1 + 2, e \\
& \quad \langle 4, (e)_1 + 2, \langle5, 2\rangle, \\
& \quad \quad \langle 4, (e)_1 + 2, \langle 5, 2\rangle, \\
& \quad \quad \quad \langle1, (e)_1 + 2, 0\rangle, \\
& \quad \quad \quad \langle1, (e)_1 + 2, 1\rangle \\
& \quad \quad \rangle \\
& \quad \quad \langle 1, (e)_1 + 2, 1\rangle \\
& \quad \rangle \\
& \quad \langle 1, (e)_1 + 2, 2\rangle, \\
& \quad \vdots \\
& \quad \langle 1, (e)_1 + 2, (e)_1 + 1\rangle \\
&\rangle
\end{aligned}
$$

确实是一个原始递归函数。假设这个编码是 $p$，我们定义

$$
rc(e) = S_{n + 2}^2(p, p, e)
$$

则

$$
\begin{align}
\{rc(e)\}(\vec{x}) &= \{S_{n + 2}^2(p, p, e)\}(\vec{x}) \\
&= \{p\}(p, e, \vec{x}) \\
&= \{e\}(S_{n + 2}^2(p, p, e), \vec{x}) \\
&= \{e\}(rc(e), \vec{x})
\end{align}
$$

推论 2.7. 对于任意的 $e$ 都存在一个 $n$ 使得 $\{n\}(\vec{x}) = \{e\}(n, \vec{x})$。

推论 2.8. 如果 $\{e\}$ 是原始递归的，则方程 $\{f(e)\}(\vec{x}) = \{e\}(f(e), \vec{x})$ 的解也是原始递归的。

仿造编程语言理论中打造递归函数的手法（即多传入一个 self 的参数，然后套上 $Y$ 组合子），我们这里也可以对常见的递归函数写出其编码。但我们默认读者熟悉编程语言理论里面的这样一套东西，所以此处不写。因此

定理 2.9. 若 $f$ 是递归的，那么 $\varphi(\vec{x}) = \mu y [f(y, \vec{x}) = 0]$ 是部分递归函数。

证明.

实现此函数只需要一层递归，套用递归定理即可。

定理 2.10. 递归函数对原始递归封闭。即若 $g, h$ 都是递归的，那么

$$
\begin{cases}
f(0, \vec{x}) = g(\vec{x}) \\
f(y + 1, \vec{x}) = h(f(y, \vec{x}), \vec{x}, y)
\end{cases}
$$

也是递归的。

证明.

原始递归无非是一次分支判断加上递归，而这两种操作在前文中均有提及。

进而

定理 2.11. 所有原始递归函数都是递归的。

证明.

初始函数被定义 2.2 的前三条包含，复合操作被定义 2.2 的第五条包含，原始递归封闭性由定理 2.10 给出。

而反过来，事实上部分递归函数无非是原始递归函数加上至多一次最小化。有下面的定理：

定理 2.12（标准型定理）. 存在一个原始递归的谓词 $T$ 满足

$$
\{e\}(\vec{x}) = ((\mu z) T(e, \langle\vec{x}\rangle, z))_0
$$

我们并不打算详细证明这个定理，只对其主旨进行阐释：

这里的 $z$ 是某种对计算过程的编码，比如每一步由何函数调用何参数（可能是子计算过程的结果）得到何结果。我们可以构造一个原始递归谓词 $C(z)$ 来检验 $z$ 是否确实是某个计算过程的编码。然后 $T$ 无非是

$$
C(z) \wedge e = (z)_2 \wedge \langle x\rangle = (z)_1
$$

状物，自然也是原始递归的。事实上你可以发现证明的复杂性主要来自计算过程的编码方式问题和 $C$ 的描述，无非是一些繁杂琐碎的工作。

递归可枚举集合

本节形式化几个数理逻辑中常见但先前从未说明的概念，如递归可枚举性、可判定性等。

定义 3.1.

  1. 一个集合（也就是一元关系）称为（递归）可判定的，若它是递归的（参见前一节定义 2.4）。
  2. 一个集合是递归可枚举的，如果它是某一个部分递归函数的定义域。$A$ 是递归可枚举的简称“$A$ RE”。
  3. 集合 $W_e^k = \{ \vec{x}\in \mathbb{N}^k : \exists y (\{e\}(\vec{x}) = y)\}$ 是递归可枚举集合定义给出的相等集合。称 $e$ 是 $W_e^k$ 的 RE-指标。由于 $e$ 本身蕴含了输入元数 $k$，我们今后将直接简写 $W_e$。

接下来我们将以 $\varphi(\vec{x})\downarrow$ 称 $\varphi(\vec{x})$ 收敛，类似地以 $\varphi(\vec{x})\uparrow$ 称 $\varphi(\vec{x})$ 发散。

可以直观地认为递归可枚举就是被抽象机接受的集合。但是这里的定义可能和术语的意思有些出入，直观地看“递归可枚举”应当是某种值域而非上方所说的定义域。事实上，有下面的定理：

定理 3.2. 下面的说法等价：（$A\subseteq \mathbb{N}$）

  1. 存在部分递归函数 $\varphi$ 使得 $A = Dom(\varphi)$；
  2. 存在部分递归函数 $\varphi$ 使得 $A = Ran(\varphi)$；
  3. 存在递归的关系 $R$ 使得 $A = \{x : \exists y R(x, y)\}$。

证明.

  • $(1)\Rightarrow (2)$。只需要构造一个定义域和值域一致的函数即可，类似于 $\psi(x) = x \cdot C_1(\varphi(x))$。

  • $(2)\Rightarrow (3)$。假设 $\varphi = \{g\}$，将 $R$ 定义为

    $$
    R(x, y) = T(g, (y)_0, (y)_1) \wedge x = (y)_{1, 0}
    $$

    Remark. 这里的 $y$ 编码了一个有序对（输入和计算过程），$T$ 取自标准型定理。

  • $(3)\Rightarrow (1)$。令 $\varphi(x) = \mu y R(x, y)$ 即可。

定理 3.2 中，第 $1$ 条即是原始的定义，第 $2$ 条符合直观想象，第 $3$ 条将抽象的定义域、值域变成了一个递归的关系，而先前我们已经研究过了递归的关系的诸多封闭性，这帮助我们导出下面的结论：

特别地，我们可以证明一个递归的集合 $A$ 一定是递归可枚举的，因为它是下述函数的定义域：

$$
\mu y [K_A(\vec{x}) = y \wedge y \ne 0]
$$

定理 3.3.

  1. 若 $A, B$ 都 递归可枚举，那么 $A \cap B$，$A\cup B$ 也递归可枚举。
  2. 若 $R(x, \vec{y})$ 递归可枚举，那么 $\exists x R(x, \vec{y})$ 也递归可枚举。本条指出递归可枚举集合的“投影”也递归可枚举。
  3. 若 $R(x, \vec{y})$ 递归可枚举，$\varphi$ 部分递归，那么 $R(\varphi(\vec{y}, \vec{z}), \vec{y})$ 也递归可枚举。
  4. 若 $R(x, \vec{y})$ 递归可枚举，那么 $\exists x < z R(x, \vec{y})$ 和 $\forall x < z R(x, \vec{y})$ 也递归可枚举。

证明.

  1. 我们以 $A\cap B$ 为例说明这个情形是容易证明的。

    $A, B$递归可枚举换言之存在递归的关系使得 $\vec{y}\in A \Leftrightarrow \exists x, R_A(x, \vec{y})$，且 $\vec{y}\in B \Leftrightarrow \exists x, R_B(x, \vec{y})$。

    用一个数编码有序对立即得到

    $$
    \vec{y}\in A\cap B \Leftrightarrow \exists x (R_A((x)_0, \vec{y})\wedge R_B((x)_1, \vec{y}))
    $$

    递归的关系对于 $\wedge$ 是封闭的，上式契合 $A\cap B$递归可枚举的等价定义。

  2. 等价定义给出递归的关系 $S$ 满足 $R(x, \vec{y}) \Leftrightarrow \exists z S(z, x, \vec{y})$。于是

    $$
    \begin{aligned}
    \exists x R(x, \vec{y}) &\Leftrightarrow \exists x \exists z S(z, x, \vec{y}) \\
    &\Leftrightarrow \exists x S((x)_0, (x)_1, \vec{y})
    \end{aligned}
    $$

    符合等价定义。

  3. 假设 $R(x, \vec{y})$ 是 $\psi(x, \vec{y})$ 的定义域，那么 $R(\varphi(\vec{y}, \vec{z}), \vec{y})$ 无非是 $\psi(\varphi(\vec{y}, \vec{z}), \vec{y})$ 的定义域。

  4. 加上有界全称量词无非是在某一个递归的函数外面套上一层原始递归，因此还是递归可枚举的。

    加上有界存在量词和加上存在量词区别不大，无非是增加一个 $(x)_0 < z \wedge …$。

定理 3.4. 部分递归函数的图像是递归可枚举的；对于一个递归可枚举的图像 $G$，存在一个部分递归函数，其图像恰好是 $G$。

图像系指 $\{(\vec{x}, y) : y = f(\vec{x})\}$。

证明.

  • 先证明部分递归函数的图像是递归可枚举的。该图像 $G = \{ (\vec{x}, y) : y = \{e\}(\vec{x}) \}$。那么
    $$
    (\vec{x}, y) \in G \Leftrightarrow \exists z T(e, \langle \vec{x}\rangle, z) \wedge y = (z)_0
    $$

    定理 3.2.3 表明其确实是递归可枚举的。

  • 然后证明函数图像递归可枚举可推出函数部分递归。$G$ 递归可枚举导出存在递归的关系 $R$ 使得 $(\vec{x}, y)\in G \Leftrightarrow \exists z, R(\vec{x}, y, z)$。那么该函数等于
    $$
    (\mu w, R(\vec{x}, (w)_0, (w_1)))_0
    $$

定理 3.5. $A$ 是递归的等价于 $A$ 和其补 $A^c$ 都是递归可枚举的。

证明.

$\Rightarrow$ 是显然的：比如说对于 $A$，有 $A(\vec{x}) \Leftrightarrow \exists y A(\vec{x})$。$A^c$ 是同样的套路。

$\Leftarrow$：假设 $A(\vec{x}) \Leftrightarrow \exists y R(\vec{x}, y), A^c(\vec{x}) \Leftrightarrow \exists y S(\vec{x}, y)$。由于 $\forall x, A(\vec{x})\vee A^c(\vec{x})$，我们可以证明 $\forall x, \exists y R(\vec{x}, y) \vee S(\vec{x}, y)$。那么 $f(\vec{x}) = \mu y [R(\vec{x}, y)\vee S(\vec{x}, y)]$ 是递归的，那么 $R(\vec{x}, f(\vec{x}))$ 也是递归的，这正是 $A$。

定理 3.6. $\psi_1, …, \psi_k$ 是部分递归函数，$R_1, …, R_{k}$ 是互斥的递归可枚举的关系，那么下列函数是部分递归函数：

$$
\varphi(\vec{x}) = \begin{cases}
\psi_i(\vec{x}) & \text{if $R_i$(\vec{x})} \\
\uparrow & \text{otherwise.}
\end{cases}
$$

证明.

假设 $\psi_i$ 的图像是 $G_i(\vec{x}, y)$，根据定理 3.4 这一定是递归可枚举的。考虑 $\varphi$ 的图像：

$$
G(\vec{x}, y) \Leftrightarrow \bigvee_{i=1}^k (R_i(\vec{x})\wedge G_i(\vec{x}, y))
$$

是递归可枚举的，因此 $\varphi$ 是递归的。

在接下来的讨论当中，我们将会看到“可判定性”（参见定义 3.1.2）并非是一切集合都具有的性质，甚至递归可枚举的集合都不一定是递归的。读者可以仔细体味其中精妙的“对角线法”的使用（导出了集合 $K$ 的定义），而集合 $K$ 的定义之外的构造都有自然的动机。

例子（图灵停机问题）. 本文定义部分递归函数使用的“抽象机”形式和图灵机十分类似，因此我们使用本文的语言来重述图灵停机问题。

问题： 集合 $\{(x, y) : \exists z : T(x, y, z)\}$ 是不是可判定的？

其中 $T$ 来自上一节的标准型定理，即是否存在一个递归的函数来判定抽象机 ${x}$ 在输入 $y$ 上是否停机。（若是，则存在一个计算过程 $z$）。

假设是，那么 $K = \{x : \exists z T(x, x, z)\}$ 亦是递归的。$K$ 是一个递归的函数的投影，其必然是递归可枚举的。现在假设 $K^c$ 也是递归可枚举的，若 $K^c = W_e$，那么 $x\in K^c \Leftrightarrow \exists z T(e, x, z)$，此时无论 $e\in K$ 还是 $e\in K^c$ 均推出对方，矛盾。因此集合 $\{(x, y) : \exists z : T(x, y, z)\}$ 是不可判定的。

集合 $\{x : \forall \vec{v}, \{x\}(\vec{v})\downarrow\}$ 是不可判定的。即无法判断一个抽象机是否在所有输入上都停机。

假设该集合是可判定的，那么存在一个递归的函数使得 $f(\vec{x}) = 0 \Leftrightarrow \forall \vec{v}, {x}(\vec{v})\downarrow$。考虑下面的原始递归函数（$K$ 的定义见上一个例子）：

$$
\varphi(\vec{x}, y) = \mu z, \vec{x} \in K
$$

假设其编号为 $e$，定义 $h(x) = S_{n + 1}^1(e, \vec{x})$，此函数是递归的，于是 $f(h(\vec{x}))$ 是递归的。然而此函数可以判定 $K$，导出矛盾。于是该集合并不可判定。

“$W_e$ 是递归的”是不可判定的。考虑

$$
\varphi(x, y) = \begin{cases}
1 & \exists z. T(x, x, z) \\
K(y) & \text{otherwise}
\end{cases}
$$

根据定理 3.6 此函数是部分递归的（其思想是，若 $x\in K$ 则返回一个递归的函数，否则返回一个非递归的函数）。用 $S^n_m$ 定理将其 Curry 化为 $\{g(x)\}(y)$。则判定 $g(x)$ 是否是递归的可以判定 $K$。

下面的不可判定性应该是显然的：

  • “$W_e$ 是有限的”是不可判定的。否则，可以通过判定 $W_{h(x)}$ 是否是有限的来判定 $K$。
  • “$W_x = W_y$”是不可判定的。否则可以通过判定 $W_{h(x)} = W_{c}$（${c}$ 是一个常函数）来判定 $K$。

这里剩了一些内容，包括 recursively separable, effectively separable, productive 相关的内容，因为精力原因选择跳过，大概也不会用到。

皮亚诺算术

本节中我们快速回顾所谓的皮亚诺算术 $\mathbf{PA}$。这是一个定义在一阶逻辑上的系统。其字母表在一阶逻辑基础上增加了：

  • 函数 $S, +, \cdot, pow$，
  • 关系 $=, \ne$，
  • 常量 $\bar{0}, \bar{1}, …$。在上下文能够推出、无需额外强调的情况下，我们会混同 $n$ 和 $\bar{n}$。

包含如下公理：

  • $\forall x (S(x)\ne 0)$，
  • $\forall xy (S(x)=S(y)\rightarrow x=y)$，
  • $\forall x (x + 0 = x)$，
  • $\forall xy (x+S(y)=S(x+y))$，
  • $\forall x (x\cdot0 = 0)$，
  • $\forall xy (x\cdot Sy = x\cdot y + x)$，
  • $\forall x (x^0 = 1)$，
  • $\forall xy (x^{Sy}) = x^y\cdot x$，
  • $\varphi(0) \wedge \forall x (\varphi(x)\rightarrow \varphi(Sx)) \rightarrow \forall x \varphi(x)$。

在此结构中，用于编码和解码的素数、整除等理论可以方便地在此系统中被形式化为关系，我们取一个复杂程度恰到好处的语句作为例子。

我们形式化“第 $x$ 个素数是 $y$”。这里我们将使用一种巧妙的方法来限制素数的个数：考虑一个乘积

$$
z = \prod_{i=1}^{x} p_i^{i}
$$

提取指标为 $x$ 的素数，即得到第 $x$ 个素数。那么 $p_x = y$ 可以被形式化为：

$$
\exists z (2^1 || z \wedge (\forall u < y \forall v \leq y (SP(u, v)\rightarrow (\forall w (u^w || z \rightarrow v^{w + 1} || z)))) \wedge (y^x || z))
$$

其中 $x^y ||z$ 表示“恰好整除”即 $x^y | z \wedge \neg x^{y+1}|z$，$SP(u, v)$ 表示 $v$ 是 $u$ 的下一个素数，是容易形式化的。

下面的引理是显然的：

引理 4.1. 对于任意闭项 $t$ 存在常量 $\bar{n}$ 使得 $\vdash t = \bar{n}$。

很不幸 $\mathbf{PA}$ 并非完备，书上指出它在两个平凡的子集 $\Delta_0, \Sigma_1$ 上完备。但这两个子集实在是太平凡，我们并不打算在此花费笔墨。

可表示性

本节将会把上述的递归函数等概念和形式逻辑重新联系起来。

定义 5.1（可表示性）.

  • 称一个合式公式 $\varphi(x_0, …, x_{n - 1}, y)$ 表示一个 $n$ 元函数 $f$，若对于任意的 $k_0, …, k_{n - 1}$ 都有

    $$
    f(k_0, …, k_{n - 1}) = p \Rightarrow \vdash \forall y (\varphi(\overline{k_0}, …, \overline{k_{n - 1}}, y) \leftrightarrow y = \bar{p})
    $$

  • 称一个合式公式 $\varphi(x_0, …, x_{n - 1})$ 表示了一个谓词 $P$ 若对于任意的 $k_0, …, k_{n - 1}$ 都有

    $$
    P(k_0, …, k_{n - 1}) \Rightarrow \vdash \varphi(\overline{k_0}, …, \overline{k_{n - 1}})
    $$

    和

    $$
    \neg P(k_0, …, k_{n - 1}) \Rightarrow \vdash \neg \varphi(\overline{k_0}, …, \overline{k_{n - 1}})
    $$

  • 称项 $t(x_0, …, x_{n - 1})$ 表示了函数 $f$ 若对于任意的 $k_0, …, k_{n - 1}$ 都有

    $$
    f(k_0, …, k_{n - 1}) = p \Rightarrow \vdash t(\overline{k_0}, …, \overline{k_{n - 1}}) = \overline{p}
    $$

首先声明用于表示函数的合式公式 $\varphi$ 其实也是具有函数性的：

引理 5.2. 对于 $k$ 元函数 $f$ 和合式公式 $\varphi$，$\varphi$ 表示了 $f$ 当且仅当

$$
f(n_0, …, n_{k - 1}) = m \Rightarrow \vdash \varphi(\overline{n_0}, …, \overline{n_{k - 1}}, \overline{m}) \text{ and } \vdash \exists!z\varphi(\overline{n_0}, …, \overline{n_{k - 1}}, z)
$$

由定义立即导出。

此外上述可表示性之间有诸多联系。用项表示是用函数表示的直接弱化（可以写出表达式的函数即可以用项表示）；谓词能被表示则理应有特征函数能被表示。具体地：

引理 5.3. 若 $f$ 可以被项表示，那么 $f$ 可以被合式公式表示。

证明.

假设 $f$ 可以被项 $t$ 表示，那么可以被

$$
\varphi(\vec{x}, y) := t(\vec{x}) = y
$$

表示。

引理 5.4. $P$ 是可表示的当且仅当其特征函数 $K_P$ 是可表示的。

证明.

$\varphi(x)$ 表示 $P$ 则 $\psi(x, y) = (\varphi(x) \wedge (y = 1) \vee (\neg \varphi(x) \wedge (y = 0)))$ 表示 $K_P$。

$\psi(x, y)$ 表示 $K_P$ 则 $\varphi(x, 1)$ 表示 $P$。

验证工作十分平凡，留给读者。

名词对照表

此处诸术语的中文翻译来源于笔者对所阅数理逻辑科普材料的记忆，因此可能与专业译名有出入，兹列出对照表以供参考：

翻译 原词
原始递归函数 primitive recursive functions
初始函数 initial function
类 class
$k$ 元关系 $k$-nary relation
有界量词 bounded quantification
有界最小值 bounded minimization
值过程函数 course-of-value function
递归可枚举 recursively enumerable
部分递归函数 partial recursive functions
抽象机 abstract machine
RE-指标 RE index
闭项 closed term
可表示性 Representability