9. 递归与公理

9.1原始递归函数

本节与下节介绍基础的递归论知识, 以应用于不完备性定理的证明. 为了简便, 我们略去与图灵机有关的全部内容.

定义 9.1.1 (原始递归函数). 我们先来定义最简单的一类 ${\omega }^{{\omega }^n}$ 上的可定义函数. 首先, 我们指定以下三个函数为初始函数:

1.	零函数 $\mathrm{Z}(x)=0$
2.	后继函数 $\mathrm{succ}(x)=x+1$
3.	投射函数 ${\pi }_{\mathrm{i}}^{\mathrm{n}}(x_1,...,x_n)=x_i$

对 $n\in \omega$, 我们称 $g:{\omega }^n\to \omega$ 与 $h:{\omega }^{n+2}\to \omega$ 经原始递归得到 $f:{\omega }^{n+1}\to \omega$, 若它满足:

1.	$f(x_1,...,x_n,0)=g(x_1,...,x_n)$
2.	$f(x_1,...,x_n,\mathrm{succ}(y))=h(x_1,...,x_n,y,f(x_1,...,x_n,y))$

包括所有初始函数, 且对函数复合和原始递归两种操作封闭的最小的全函数类中的元素称作原始递归函数.

注 9.1.2. 不难证明, 每个原始递归函数都对应不唯一的一个有限函数列, 其中每个函数都是初始函数, 或由之前的函数复合而成, 或由之前的函数原始递归而成. 这称为它的生成序列.

我们首先指出, 许多常见的函数都是原始递归的.

定理 9.1.3. 以下函数均为原始递归函数:

1.	常函数 ${\mathrm{C}}_{\mathrm{k}}^{\mathrm{n}}:{\omega }^n\to \{k\}$
2.	前驱 $\mathrm{pred}:\omega \to \omega$, $0$ 的前驱仍为 $0$.
3.	加法 $+:{\omega }^2\to \omega$
4.	乘法 $\times :{\omega }^2\to \omega$
5.	指数 ${}^{:}{\omega }^2\to \omega$
6.	阶乘 $!:\omega \to \omega$
7.	截断减法 $-:{\omega }^2\to \omega$, 小数减去大数全作为 $0$ 处理.
8.	取商 $/:{\omega }^2\to \omega$, 这是小学学的带余除法的商.
9.	取余数 $\%:{\omega }^2\to \omega$
10.	零特征函数 $\delta :\omega \to \omega$, 它只在 $0$ 处取 $1$, 在别的地方均取 $0$.

证明. 略.

$\square$

上面列举的最后一个原始递归函数的名字给予我们一些想法.

定义 9.1.4 (原始递归集合). 对一个集 $R\subseteq {\omega }^n$, 我们称 ${\chi }_R:{\omega }^n\to \omega$ 为其特征函数, 它在 $R$ 上恒为 $1$, 在别处恒为 $0$.

一个集合 $R\subseteq {\omega }^n$ 称作原始递归集合, 若其特征函数是原始递归函数.

定理 9.1.5. 原始递归集合对取补集、有限并集和有限交集封闭.

证明. 略.

$\square$

同样, 许多常见的关系作为集合都是原始递归的.

定理 9.1.6. 以下谓词/关系作为集合是原始递归的:

1.	等于 $=$
2.	小于等于 $\le$
3.	整除 $|$
4.	素数判断 $\mathrm{isPrime}$
5.	合数判断 $\mathrm{isCompN}$

证明. 略.

$\square$

推论 9.1.7. $p:\omega \to \omega$ 是原始递归函数, 它对 $n$ 给出第 $n+1$ 个素数.

我们还可以有分段定义函数.

定理 9.1.8. 若 $f_1$ 与 $f_0$ 均为原始递归函数, $R$ 是原始递归集合, 则 $f$ 也是原始递归函数, 它在 $R$ 上取值为 $f_1$ 的值, 在 $R$ 之外取值为 $f_0$ 的值.

证明. 略.

$\square$

最后, 我们指出两种操作, 原始递归函数类对这两者封闭.

定义 9.1.9 (有界极小算子). 对一个 $P\subseteq {\omega }^{n+1}$, 我们定义 $f(\bar{x},y)=\mu z\le y((\bar{x},z)\in P)$ 是最小的满足 $(\bar{x},z)\in P$ 的不大于 $y$ 的 $z$; 如果这样的 $z$ 不存在, 则此式取值为 $\mathrm{succ}(y)$. 这个 $\mu$ 读作最小的.

定理 9.1.10. 若 $P$ 是原始递归集合, 则 $f(\bar{x},y)=\mu z\le y((\bar{x},z)\in P)$ 是原始递归函数, $E=\{(\bar{x},y)|\exists z\le y((\bar{x},z)\in P)\}$ 和 $A=\{(\bar{x},y)|\forall z\le y((\bar{x},z)\in P)\}$ 是原始递归集合.

证明. 只需注意以下引理.

引理 9.1.11. 若 $f(\bar{x},y)$ 原始递归, 则 $Su(\bar{x},z)={\sum }_{y\le z}f(\bar{x},y)$ 与 $Pr(\bar{x},z)={\prod }_{y\le z}f(\bar{x},y)$ 也都是原始递归的.

证明. 略.

$\square$

注意 $\mu z\le y((\bar{x},z)\in P)={\sum }_{z\le y}{\prod }_{r\le z}{\chi }_{\neg P}(\bar{x},r)$, ${\chi }_A={\prod }_{z\le y}{\chi }_P$ 和 ${\chi }_E=1-{\prod }_{z\le y}{\chi }_{\neg P}$ 即可.

$\square$

定义 9.1.12 (强递归). 对 $f:{\omega }^{k+1}\to \omega$, 我们称 $F(\bar{x},n)={\prod }_{k\le n}p(k{)}^{f(\bar{x},k)+1}$ 为 $f$ 的历史函数.

如果我们称 $f$ 是由 $g$ 和 $h$ 经强递归得到的, 若:

1.	$f(\bar{x},0)=g(\bar{x})$
2.	$f(\bar{x},\mathrm{succ}(y))=h(\bar{x},y,F(\bar{x},y))$

定理 9.1.13. 原始递归函数强递归得到的函数也是原始递归的.

证明. 显然此时历史函数也是原始递归的.

$\square$

9.2递归函数

现在, 我们要考虑比原始递归函数更广义的两类可计算函数, 分别是递归全函数与部分递归函数.

定义 9.2.1 (正则极小算子). 对全函数 $f:{\omega }^{n+1}\to \omega$, 若 $\forall \bar{x}\exists y(f(\bar{x},y)=0)$, 则称 $f$ 有正则性条件. 我们对有正则条件的 $f$ 定义 $g(\bar{x})=\mu y(f(\bar{x},y)=0)$ 为 $f$ 经过正则极小算子 $\mu$ 得到的函数, 它是最小的使得 $f(\bar{x},y)=0$ 的 $y$.

定义 9.2.2 (递归全函数). 包含全体初始函数, 且对复合、原始递归与正则极小化封闭的最小的全函数类中的函数称作递归全函数.

然而, 很多时候我们并不能事先确定正则条件是否成立 (正如我们不知道程序是否停机), 因此对部分函数定义极小算子是有必要的.

定义 9.2.3 (极小算子). 对部分函数 $f$, 我们称 $g(\bar{x})=\mu y(\forall z\le y(f(\bar{x},z)\downarrow )\wedge f(\bar{x},y)=0)$ 是 $f$ 经过极小算子得到的函数, 这里 $f(\bar{x},z)\downarrow$ 指的是 $f$ 在此时有定义, $mu$ 仍然读作最小的.

定义 9.2.4 (部分递归函数). 包含全体初始函数, 且对复合、原始递归与极小化封闭的最小的部分函数类中的函数称作部分递归函数.

考察部分递归函数而非递归全函数的好处是, 部分函数存在通用函数, 而全函数不存在.

定理 9.2.5 (Kleene, 通用函数定理). 存在原始递归函数 $U:\omega \to \omega$ 与原始递归集 $T\subseteq {\omega }^3$, 使得对任意的部分递归函数 $f:\mathrm{dom}(f)\subseteq \omega \to \omega$ 都存在一个自然数 $e$ 使得 $f(x)=U(\mu z((e,x,z)\in T))$.

进一步, 存在通用部分递归函数 $\Phi :{\omega }^2\to \omega$, 使得对任何部分递归函数 $f:\omega \to \omega$ 都存在自然数 $e$ 满足 $f(x)=\Phi (e,x)$.

证明. 这个 Kleene’s T 指的其实是 $(e,x,z)\in T$ 当且仅当程序 $e$ 对输入 $x$ 的计算过程的编码为 $z$, 其中细节其实就是证明部分递归函数等价于图灵可计算函数的过程, 此处略.

$\square$

定理 9.2.6. 不存在通用递归全函数.

证明. 对角线论证. 如果存在 $T:{\omega }^2\to \omega$ 对所有 $f:\omega \to \omega$ 通用, 考虑 $f(x)=T(x,x)+1$. 它必须是某个 $f(x)=T(e,x)$, 于是 $T(e,e)=T(e,e)+1$, 显然矛盾.

$\square$

递归全函数与部分递归函数满足一个字面的关系.

定理 9.2.7. 函数的递归全函数当且仅当它是全的部分递归函数.

证明. $\Rightarrow$: 对生成序列做归纳.

$\Leftarrow$: 此时 $f(x)=U(\mu z((e,x,z)\in T))$ 和 $f$ 是全函数指出这是在对正则的原始递归谓词进行正则极小化, 所以它是递归全函数.

$\square$

递归全函数自然地给出递归集的定义.

定义 9.2.8 (递归集). 如果一个集的特征函数是递归全函数, 则称这个集是递归集.

部分递归函数则给出以下递归可枚举集的定义.

定理 9.2.9 (递归可枚举集). 对 $A\subseteq \omega$, 以下命题等价:

1.	$A$ 是一个部分递归函数的值域.
2.	$A$ 是空集或 $A$ 是一个递归全函数的值域.
3.	$A$ 是空集或 $A$ 是一个原始递归函数的值域.
4.	$A$ 是一个部分递归函数的定义域.
5.	存在原始递归集 $R\subseteq {\omega }^2$, 使得 $A=\{x|\exists y((x,y)\in R)\}$.
6.	$A$ 的部分特征函数是部分递归的, 这个部分特征函数 ${\chi }_{A_P}(x)$ 在 $A$ 上取值为 $1$, 在别处无定义.

它满足这些条件中的任意一个 (也就是全部) 时, 称它为一个递归可枚举集.

证明. 略.

$\square$

进一步, 我们可以定义 ${\omega }^n$ 上的递归可枚举集.

定理 9.2.10. 递归可枚举集对有限交、有限并、存在量化封闭, 但不对取补封闭. 其模糊集类 (对取补封闭的子类) 恰为递归集.

证明. 略.

$\square$

9.3编码与表示

接下来, 我们要在算术语言 ${\mathcal{L}}_{ar}=\{0,\mathrm{succ},+,\times \}$ 上讨论 Godel 著名的两个不完全性定理. 第一不完全性定理要求较弱, 我们取一个相当简单的理论来证明.

定义 9.3.1 (Robinson 算术). 以下理论称作 Robinson 算术, 记作 Q:

1.	$\forall x\neg (\mathrm{succ}(x)\approx 0)$
2.	$\forall x\forall y(\mathrm{succ}(x)\approx \mathrm{succ}(y)\to x\approx y)$
3.	$\forall x(\neg x\approx 0\to \exists y(x\approx \mathrm{succ}(y)))$
4.	$\forall x(x+0\approx x)$
5.	$\forall x\forall y(x+\mathrm{succ}(y)\approx \mathrm{succ}(x+y))$
6.	$\forall x(x\times 0\approx 0)$
7.	$\forall x\forall y(x\times \mathrm{succ}(y)\approx x\times y+x)$

为了区分, 以上列举的各式将被记为 (Q1) 到 (Q7).

可表示性

我们这一小节的任务是证明递归全函数就是可表示函数.

定义 9.3.2 (可表示集). 称 $P\subseteq {\omega }^k$ 是理论 $T\supseteq Q$ 中可表示的, 若存在其表示公式 $\rho (\bar{x})$, 使得 $(\bar{n})\in P\to {⊢}_T\rho (\bar{n})$, 且 $\neg (\bar{n})\in P\to {⊢}_T\neg \rho (\bar{n})$.

注 9.3.3. 注意, 否定情况是 $⊢\neg$ 而非 $\neg ⊢$, 后面的只不过是不可证明, 前者才是证明为假.

定义 9.3.4 (可表示函数). 称 $f:{\omega }^k\to \omega$ 是理论 $T\supseteq Q$ 中可表示的, 若存在其表示公式 $\varphi (\bar{x},y)$, 使得 ${⊢}_T\forall y(\varphi (\bar{n},y)\leftrightarrow y=f(\bar{n}))$.

注 9.3.5. 可表示函数的表示公式是比函数作为集合是可表示集的表示公式, 但反过来则不一定.

显然, 可表示性与可定义性某种意义上是相同的.

定理 9.3.6. 集合 $P$ 在理论 $\mathrm{Th}(\mathbb{N})$ 中被公式 $\rho$ 表示, 当且仅当它在 $\mathbb{N}$ 中被公式 $\rho$ 定义.

证明. 显然.

$\square$

进一步, 我们有以下性质.

定理 9.3.7. 可表示集对有限交、有限并和取补集封闭, 且在一致理论扩张下不变.

证明. 前面就是合取、析取与否定, 最后一个连表示公式都不用变.

$\square$

我们先来证明简单的一边.

定理 9.3.8. 可表示集是递归集.

证明. 理论是递归可枚举的, 因此我们对每组 $\bar{n}$ 递归地枚举理论中全部合法的证明序列, 直到 $P$ 的表示序列 $\rho$ 对应的 $\rho (\bar{n})$ 的证明出现, 或者其否定出现. 由定义这两个必然出现其一.

$\square$

然而, 要证明可表示函数是递归函数却并不容易, 问题就出在可表示函数的表示公式的要求比可表示集的更强这里. 不过, 我们其实可以修一修这个表示公式.

定理 9.3.9. 函数可表示当且仅当它作为集合可表示.

证明. 向右显然, 向左注意到其实我们只需要加上一层正则极小化算子, 我们其实就是在证明以下引理.

引理 9.3.10. 若 $P\subseteq {\omega }^{k+1}$ 被 $\psi (\bar{x},y)$ 表示, 且 $\omega \models \forall \bar{a}\exists b((\bar{a},b)\in P)$, 则公式 $\varphi (\bar{x},y):=\psi (\bar{x},y)\wedge \forall z<y(\neg \psi (\bar{x},z))$ 表示了函数 $f:\bar{a}\to \mu b((\bar{a},b)\in P)$.

证明. 不难有 $⊢\varphi (\bar{a},y)\leftrightarrow y\approx f(\bar{a})$.

$\square$

现在 $f$ 就是 $\bar{a}\mapsto \mu b((\bar{a},b)\in f)$.

$\square$

推论 9.3.11. 可表示函数的正则极小化是可表示函数.

为了证明可表示函数包含递归函数 (从而它们一样), 我们还要断言初始函数都是可表示函数, 以及可表示函数对复合和原始递归封闭. 下面一一验证.

定理 9.3.12. 项 $t$ 诱导出的函数 $f$ 都是可表示的.

证明. 一个包含 $k$ 个变元的项 $t=t(x_1,...,x_k)$ 自然诱导函数 $f(n_1,...,n_k)=t(n_1,...,n_k)$. 直接令公式 $\varphi (x_1,...,x_k,y):=t(x_1,...,x_k)\approx y$, 不难有
$⊢\forall y(\varphi (n_1,...,n_k,y)\leftrightarrow y\approx f(n_1,...,n_k))$.

$\square$

推论 9.3.13. 初始函数都是可表示函数.

定理 9.3.14. 若 $h_1(x_1,...,x_n)$ 到 $h_r(x_1,...,x_n)$ 都可表示, $g(y_1,...,y_r)$ 也可表示, 则 $f(x_1,...,x_n)=g(h_1,...,h_r)$ 可表示.

证明. 记 $h_i$ 的表示公式是 ${\theta }_i(\bar{x},y_i)$, $g$ 的表示公式是 $\psi (\bar{y},z)$, 则 $\varphi (\bar{x},z):=\forall y_i({\wedge }_i{\theta }_i(\bar{x},y_i)\to \psi (\bar{y},z))$ 表示 $f$.

$\square$

推论 9.3.15. 可表示函数对复合封闭.

最困难的部分是证明可表示函数对原始递归封闭, 我们需要一些数论中的熟知命题.

定理 9.3.16 (Bezout). $a,b$ 互素当且仅当存在 $u,v$ 使得 $ua+vb=1$.

定理 9.3.17. 中国剩余定理如果有限个 $d_i$ 两两互素, 则 $\mathbb{Z}\twoheadrightarrow {\prod }_i\mathbb{Z}/d_i\mathbb{Z}$ 是满射.

为了拿到充分长的两两互素的数组, 我们再给一个引理.

引理 9.3.18. 对任意 $s\le 0$, 以下 $s+1$ 个数 $k\cdot s!+1(1\le k\le s+1)$ 两两互素.

以下神奇编码过程来自 Godel.

定理 9.3.19. 构造以下可表示函数:

1.	$\alpha :{\omega }^3\to \omega ,(c,d,i)\mapsto c\%(1+d(i+1))$
2.	$J:{\omega }^2\to \omega ,(a,b)\mapsto \frac{1}{2}(a+b)(a+b+1)+a$
3.	$K:\omega \to \omega ,p\mapsto \mu a\le p\exists b\le p(p=J(a,b))$
4.	$L:\omega \to \omega ,p\mapsto \mu b\le p\exists a\le p(p=J(a,b))$
5.	$\beta :{\omega }^2\to \omega ,(s,i)\mapsto \alpha (K(s),L(s),i)$

则 $\forall n\forall a_0,...,a_n\exists s\forall i\le n(a_i=\beta (s,i))$.

证明. 略.

$\square$

我们就用这个编码证明最后一步.

定理 9.3.20. 若 $f$ 由 $f(\bar{m},0)=g(\bar{m})$ 和 $f(\bar{m},\mathrm{succ}(n))=h(\bar{m},n,f(\bar{m},n))$ 经原始递归得到, 则 $g$ 与 $h$ 均可表示时 $f$ 亦可表示.

证明. 若 $g(\bar{x})$ 被 $\varphi (\bar{x},y)$ 表示, $h(\bar{x},y,z)$ 被 $\phi (\bar{x},y,z,w)$ 表示, 则有可表示集 $P\subseteq {\omega }^{k+2}$ 由 $\varphi (\bar{m},\beta (s,0))\wedge \forall i<n(\phi (\bar{m},n,\beta (s,i),\beta (s,\mathrm{succ}(i))))\leftrightarrow (\bar{m},n,s)\in P$ 表示, 进而 $f(\bar{m},n)=\beta (\mu s((\bar{m},n,s)\in P),n)$ 可表示.

$\square$

总结如下.

定理 9.3.21. 函数递归当且仅当可表示.

编码

这一小节, 我们要用 ${\mathcal{L}}_{ar}$ 讨论自己的语法, 这是通过编码进行的. 我们的一切行为均在 $\mathbb{N}$ 上进行.

定义 9.3.22 (Godel 编码). 我们给每个语言中的符号 $\zeta$ 指定一个奇数 $♯\zeta$: $\forall$ 是 $1$, $0$ 是 $3$, $\mathrm{succ}$ 是 $5$, $+$ 是 $7$, $\times$ 是 $9$, 左右括号是 $11$ 和 $13$, $\neg$ 是 $15$, $\to$ 是 $17$, $\approx$ 是 $19$, 随后是可列个变元符号.

进一步, 我们给每个字符串 $\zeta ={\zeta }_0...{\zeta }_n$ 指定其 Godel 编码为 $♯\zeta ={\prod }_{k\le n}{p}_k^{♯{\zeta }_k+1}$.

我们额外对每个 $n+1$ 引入记号 $<>:{\omega }^{n+1}\to \omega ,<m_0,...,m_n>={\prod }_{0\le i\le n}{p}_i^{m_i+1}$, 则上式也可记为 $♯\zeta =<♯{\zeta }_i>$.

我们的目标是探索编码后的逻辑关系是否是原始递归的. 对于语言中说出的一个东西, 我们用 东西代指 $\{♯x|x$ 是这样的东西 $\}\subseteq \omega$. 我们采取前缀函数记法, 以尽量减少括号的使用.

定理 9.3.23. 变元是原始递归的.

证明. 变元 $=\{n|\exists k<n(n=2k+21)\}$

$\square$

定理 9.3.24. 项是原始递归的.

证明. $t\in$ 项有以下的递归定义, 如果以下之一成立:

1.	$\exists s<t(t=<s>\wedge (s=♯0\vee s\in$ 变元 $))$
2.	$\exists r,s<t(t=<r\square ♮s>\wedge r=♯\mathrm{succ}\wedge s\in$ 项 $)$
3.	$\exists q,r,s<t(t=<q\square ♯(\square ♮r\square ♮s\square ♯)>\wedge (q=♯+\vee q=♯\times )\wedge r,s\in$ 项 $)$

这里 $\square$ 是把两个字符串放在一起, $♮$ 把 $<n_0,...,n_m>$ 还原成自然数串 $(n_0,...,n_m)$.

$\square$

注 9.3.25. $♭$ 指的是把 $♯\zeta$ 还原成字符串 $\zeta$.

定理 9.3.26. 原子公式是原始递归的.

定理 9.3.27. 公式是原始递归的.

定理 9.3.28. 逻辑连接词与量词都是原始递归函数.

证明. 例如, ${\neg }_{♯}n=<♯(\square ♯\neg \square ♮n\square ♯)>$.

$\square$

定理 9.3.29. 变元替换是原始递归函数.

证明. 这是一个 $\mathrm{Sb}:(♯\varphi ,♯x,♯t)\mapsto ♯{\varphi }_t^x$, 进行归纳定义不难.

$\square$

定理 9.3.30. $\underline{\omega }$ 是原始递归的.

证明. 这个东西是 $\{♯{\mathrm{succ}}^n(0)|n\in \omega \}$, 换句话说我们把标准自然数编码进标准自然数里面.

$\square$

定理 9.3.31. 二元关系 自由出现 $(n,m)$ 是原始递归的.

证明. 这个指的是变元 $♭n$ 在公式或项 $♭m$ 中自由出现.

$\square$

定理 9.3.32. 语句是原始递归的.

定理 9.3.33. 三元关系 无冲突替换 $(k,m,n)$ 是原始递归的.

证明. 这个指的是项 $♭k$ 在公式 $♭m$ 中无冲突替换变元 $♭n$.

$\square$

定理 9.3.34. 二元关系 全称概括 $(m,n)$ 是原始递归的.

证明. 这个指的是 $♭m$ 是 $♭n$ 的一个全称概括.

$\square$

定理 9.3.35. 逻辑公理是原始递归的.

证明. 逐一验证之.

$\square$

我们还要讨论理论中的证明. 我们先严格地给出公理化的定义.

定义 9.3.36. 称 $X\subseteq T$ 公理化了理论 $T$, 若 $\underline{X}$ 是一个递归集, 且 $T⊢\sigma$ 当且仅当 $X⊢\sigma$.

定理 9.3.37. 对可公理化的理论 $T$, 谓词 T 中的证明序列 $(b)$ 是递归的.

证明. 这个指的是 $♮b$ 里面的数字可以用 $♭$ 解码成一个 $T$ 中的证明序列.

$\square$

定义 9.3.38. 定义谓词 ${\mathrm{bew}}_T^{\mathbb{N}}(b,a)\leftrightarrow$ T 中的证明序列 $(b)\wedge {\pi }_{\mathrm{lh}(b)}^{\mathrm{lh}(b)}(♮b)=a$ 这里 $\mathrm{lh}(b)$ 是 $♮b$ 的长度, 这个谓词读作 $b$ 在 $T$ 中证明 $a$.

注 9.3.39. 其实是 $b$ 作为证明序列解码得到 $♭a$ 的证明序列.

定理 9.3.40. ${\mathrm{bew}}_T^{\mathbb{N}}$ 是递归的.

上一小节对可表示性与递归性等价的定理在此应用为这个谓词的提升.

推论 9.3.41. 存在算术语言中可定义的谓词 ${\mathrm{bew}}_T(x,y)$, 使得它在结构 $\mathbb{N}$ 上恰为 ${\mathrm{bew}}_T^{\mathbb{N}}$.

现在, 这个 $\mathrm{bew}$ 成功地在算术语言中描述出了算术理论 $T$ 的可证明性, 摆脱了对 $\mathbb{N}$ 的依赖.

引理 9.3.42. 对可公理化的理论 $T\supseteq Q$,

1.	${⊢}_T\sigma$, 则 $\exists n\in \omega$ 满足 ${⊢}_T{\mathrm{bew}}_T({\mathrm{succ}}^n(0),{\mathrm{succ}}^{♯\sigma }(0))$.
2.	$\neg {⊢}_T\sigma$, 则 $\forall n\in \omega$ 都有 $\neg {⊢}_T{\mathrm{bew}}_T({\mathrm{succ}}^n(0),{\mathrm{succ}}^{♯\sigma }(0))$.

lemma 最后, 我们单独引入一个定义.

定义 9.3.43. 定义 $\mathrm{bwb}(y)$ 为 $\exists x(\mathrm{bew}(x,y))$.

推论 9.3.44. ${\mathrm{bwb}}^{\mathbb{N}}$ 是递归可枚举的, 且 ${⊢}_T\sigma$ 可推出 ${⊢}_T{\mathrm{bwb}}_T({\mathrm{succ}}^{♯\sigma }(0))$.

注 9.3.45. 然而, ${⊢}_T\neg \sigma$ 却并不能推出 ${⊢}_T\neg {\mathrm{bwb}}_T({\mathrm{succ}}^{♯\sigma }(0))$.

不动点

我们给出最后一个重要的引理, 它具有相当的暗示性. 我们先给出一个常见简记法.

定义 9.3.46. 对公式 $\varphi$, 我们用 $┌\varphi ┐$ 代指 ${\mathrm{succ}}^{♯\varphi }(0)$. 对自然数 $n\in \omega$, 我们用 $┌n┐$ 代指 ${\mathrm{succ}}^n(0)$.

定理 9.3.47 (不动点引理). 存在递归的算法, 任给单自由变元公式 $\psi (x)$, 这算法都给出一个句子 $\sigma$, 满足 ${⊢}_Q(\sigma \leftrightarrow \psi (┌\sigma ┐))$.

注 9.3.48. 换言之, 这个函数 $♯\psi \mapsto ♯\sigma$ 是递归的.

证明. 令递归函数 $<♯\phi ,n>\mapsto ♯\phi (n)$ 由一个公式 $\theta (x,y,z)$ 表示, 换言之 ${⊢}_Q\forall z(\theta (┌\phi ┐,┌n┐,z)\leftrightarrow z\approx ┌\phi (┌n┐)┐)$. 考察公式 $\tau (x):=\forall z(\theta (x,x,z)\to \psi (z))$, 我们所要的 $\sigma$ 正是 $\forall z(\theta (┌\tau ┐,┌\tau ┐,z)\to \psi (z))$, 也就是 $\tau (┌\tau ┐)$.

$\square$

9.4第一不完全性

现在, 我们来叙述并证明大名鼎鼎的 Godel 第一不完全性定理.

定理 9.4.1 (Godel 第一不完全性定理). 对包含 $Q$ 的递归可公理化理论 $T$, 如果 $T$ 一致, 则存在语句 $\sigma$, 满足 $\neg {⊢}_T\sigma$ 且 $\neg {⊢}_T\neg \sigma$.

这其实是 Rosser 给出的强版本定理, Godel 一开始证明的东西是这样的.

定理 9.4.2 (Godel 第一不完全性定理, 原始版本). 对包含 $Q$ 的递归可公理化理论 $T$, 如果 $T$ 是 $\omega$ 一致的, 则存在语句 $\sigma$, 满足 $\neg {⊢}_T\sigma$ 且 $\neg {⊢}_T\neg \sigma$.

这里用到了一个新概念, 我们将它与原先的概念进行对比.

定义 9.4.3. 对语言 ${\mathcal{L}}_{ar}$ 上的理论 $T$, 我们有以下两种不一致的概念:

1.	$\omega$ 不一致: 存在 $\phi (x)$ 使得 ${⊢}_T\exists x(\phi (x))$, 但 $\forall n\in \omega$ 均有 ${⊢}_T\neg \phi (┌n┐)$.
2.	不一致: 存在 $\sigma$ 使得 ${⊢}_T\sigma$ 而且 ${⊢}_T\neg \sigma$.

不是 $\omega$ 不一致就称 $\omega$ 一致, 不是不一致就称一致.

注 9.4.4. $\omega$ 不一致显然会指出自然数标准模型不是这个理论的模型, 但不一致则指出它没有模型, 可见其强度差异. 显然, 非标准模型的理论都是一致却非 $\omega$ 一致的.

我们先来看原始版本的证明.

证明. 考虑单自由变元公式 $\neg {\mathrm{bwb}}_T(x)$ 的不动点 $\sigma$, ${⊢}_T(\sigma \leftrightarrow \neg {\mathrm{bwb}}_T(┌\sigma ┐))$.

如果 ${⊢}_T\sigma$, 则 ${⊢}_T{\mathrm{bwb}}_T(┌\sigma ┐)$, 换言之 $T$ 不一致, 进而 $T$ 是 $\omega$ 不一致的, 矛盾.

如果 ${⊢}_T\neg \sigma$, 则 $T$ 的一致性指出 $\neg {⊢}_T\sigma$, 于是 $\forall n\in \omega$ 均有 $\neg {⊢}_T{\mathrm{bew}}_T(┌n┐,┌\sigma ┐)$, 而此时又有 ${⊢}_T\mathrm{bwb}(┌\sigma ┐)$, 于是这与 $T$ 的 $\omega$ 一致性发生矛盾.

$\square$

然而, 由于 $\omega$ 一致性严格强于一致性, 我们需要引入 Rosser 的一个技巧来证明第一个版本的更强的不完全性定理.

证明. 我们考虑另一个谓词, 它在 $\mathbb{N}$ 里面就是 $\mathrm{bwb}$, 但在一般情形下却比后者更容易证明. (恰好像是 $\omega$ 一致与一致的区别)

定义 9.4.5. 令 ${\mathrm{prov}}_T(x)$ 为 $\exists y({\mathrm{bew}}_T(y,x)\wedge \forall z<y(\neg {\mathrm{bew}}_T(z,{\neg }_{♯}x)))$.

以下我们固定一个一致的算术理论 $T$, 然后略去下标 $T$ 以便叙述. 我们引入以下重要性质.

引理 9.4.6. 比 $\mathrm{bwb}$ 更好的是, $\mathrm{prov}$ 同时具有以下性质:

1.	$⊢\sigma$ 推出 $⊢\mathrm{prov}(┌\sigma ┐)$
2.	$⊢\neg \sigma$ 推出 $⊢\neg \mathrm{prov}(┌\sigma ┐)$

证明. 第一个式子对 $\mathrm{bwb}$ 成立, 显然也对 $\mathrm{prov}$ 成立. 第二个式子在 $T$ 一致时对 $\mathrm{bwb}$ 不一定成立, 必须要 $T$ 的 $\omega$ 一致才能成立, 但此时却可以通过比较证明编码的大小来证明对 $\mathrm{prov}$ 成立.

$\square$

我们只要考虑 $\neg \mathrm{prov}$ 的不动点 $\sigma$, 就可以验证 $\neg ⊢\sigma$ 和 $\neg ⊢\neg \sigma$ 了.

$\square$

最后, 我们再讨论一个语义版本的定理.

定理 9.4.7 (Tarski 真不可定义定理). $\underline{\mathrm{Th}(\mathbb{N})}$ 是作为 ${\mathcal{L}}_{ar}$ 结构的 $\mathbb{N}$ 的不可定义集.

证明. 否则, 如果 $\underline{\mathrm{Th}(\mathbb{N})}$ 被公式 $\phi (x)$ 定义, 对 $\neg \phi$ 使用不动点引理就得到 $\mathbb{N}\models \sigma$ 当且仅当 $\mathbb{N}/\models \phi (┌\sigma ┐)$, 产生矛盾.

$\square$

类似地运用不动点引理, 还可以证明一大堆这样的如同不完全性一样的定理. 我们这里列举其一, 目的在于说明问题正在于递归 (可判定) 的要求太强.

定理 9.4.8 (Q 的强不可判定性). 任何算术理论 $T$, 若 $T\cup Q$ 是完全且一致的, 则 $T$ 是不可判定的.