归纳和递归

归纳

归纳是一类经常出现在逻辑和数学其他分支中的特殊构造方法。我们考虑初始集合 $B$ 和全集 $U$，以及若干函数组成的函数类 $\mathcal{F}$。集合 $C$ 就是利用 $B$ 中的元素和 $\mathcal{F}$ 中的函数构造出来的最小封闭集合。

对于集合 $C$，有两种主要的定义。“自上而下”的定义为：设归纳子集 $S$ 满足 $B\subseteq S$ 且 $S$ 是 $\mathcal{F}$ 的封闭集合，则定义 $C^{\ast }$ 为 $U$ 的所有归纳子集 $S$ 的交集。而“自下而上”的定义为：设 $C_{\ast }$ 是由 $B$ 中的元素有限次使用 $\mathcal{F}$ 中的函数构造出来的集合，其构造序列为 $⟨x_0,x_1,\cdots ,x_n⟩$，使得对于每个 $i\le n$，有下面二式至少有一式成立：

1. $x_i\in B$；
2. 存在 $f\in \mathcal{F}$ 使得 $x_i=f(x_{a_1},x_{a_2},\cdots ,x_{a_m})$，其中 $m$ 为 $f$ 的元数，$a_1,a_2,\cdots ,a_m<i$。

我们可以证明 $C^{\ast }=C_{\ast }$。因此，我们构造出来了一个集合 $C$，它是由 $B$ 中的元素和 $\mathcal{F}$ 中的函数构造出来的最小封闭集合。

归纳法则

假设 $C$ 是由 $B$ 中的元素通过 $\mathcal{F}$ 生成的，如果 $S$ 是 $C$ 的一个子集，$S$ 包含 $B$ 并且在 $\mathcal{F}$ 下封闭，那么 $S=C$。

递归

递归更像归纳的逆运算，同时也是一种扩展。考虑全集 $U$ 和子集 $B$，以及两个函数 $f$ 和 $g$，其中 $f$ 是从 $U\times U$ 到 $U$ 的函数，$g$ 是从 $U$ 到 $U$ 的函数，$C$ 是由在函数 $f$ 和 $g$ 作用下生成的集合。

下面我们定义在 $C$ 上面的函数，假设定义（这里的 $\overline{h}$ 可以看作 $B$ 的一个真值指派的扩展）

1. 对于 $x\in B$，计算 $\overline{h}(x)$ 的规则；
2. 若 $\overline{h}(x)$ 和 $\overline{h}(y)$ 已知，计算 $\overline{h}(f(x,y))$ 或者 $\overline{h}(g(x))$ 的规则。

可以看出，函数 $\overline{h}$ 可能不是良定义的。譬如对于实数集 $U$ 和 $B=\{0\}$，定义 $f(x,y)=xy$ 和 $g(x)=x+1$，如果我们定义

1. $\overline{h}(0)=0$
2. $\overline{h}(f(x,y))=f(\overline{h}(x),\overline{h}(y))$
3. $\overline{h}(g(x))=\overline{h}(x)+2$

那么，我们会发现 $\overline{h}$ 并不是良定义的。例如，我们在计算 $\overline{h}(1)$ 时会发现 $1=g(0)=f(g(0),g(0))$。那么，对于一个生成的 $C$，是否总能找到合适的 $\overline{h}$ 呢？我们下面就来介绍递归定理。

递归定理

称 $C$ 在函数集 $\mathcal{F}$ 的作用下自由生成当且仅当

1. $\mathrm{\forall }{f}_i\in \mathcal{F}$，$f_i$ 是单射；
2. $\mathrm{\forall }{f}_i,f_j\in \mathcal{F}$，$\mathrm{ran}(f_i)\cap \mathrm{ran}(f_j)=\mathrm{\varnothing }$

设 $U$ 的子集 $C$ 是由 $B$ 在函数集 $\mathcal{F}$ 的作用下自由生成的，其中对于任意 $f_i\in \mathcal{F}$ 我们有

$$f_i:U^{n_i}\to U$$

其中 $n_i$ 是 $f_i$ 的元数。有集合 $V$ 、函数集 $\mathcal{G}$ 和函数 $h$ 使得对于任意 $g_i\in \mathcal{G}$，有

$$\begin{array}{c}{g}_i:V^{n_i}\to V\\ h:B\to V\end{array}$$

那么，存在唯一的函数 $\overline{h}:C\to V$ 使得

1. 对于 $B$ 中的 $x$，$\overline{h}(x)=h(x)$
2. 对于函数集 $\mathcal{G}$ 中的每一个函数 $g_i$，对任意的 $x_1,x_2,\cdots ,x_{n_i}\in C$，有

$$\overline{h}(f_i(x_1,x_2,\cdots ,x_{n_i}))=g_i(\overline{h}(x_1),\overline{h}(x_2),\cdots ,\overline{h}(x_{n_i}))$$

因此，我们可以看出，只要我们选取得足够仔细，那么就总是可以找到合适的 $\overline{h}$ 来扩展原来的 $h$，并且这样的 $\overline{h}$ 是唯一的。另一方面，从代数的角度上来看，这个定理说明了从 $B$ 到 $V$ 的任何映射 $h$ 都可以扩展到从 $C$ 到 $V$ 上面的同态。

例如，我们可以证明，存在唯一的函数 $\overline{h}$，它将一个合式公式映射到一个正整数，表示该合式公式的长度。这是因为显然合式公式的构造运算函数都满足两两不相交和单射，那么这就是自由生成。此外，$\overline{h}$ 满足（其中 $\alpha$ 和 $\beta$ 是合式公式，$\circ$ 是合式公式的构造运算）

$$\begin{array}{c}\overline{h}(A)=1,A\mathrm{为}\mathrm{命}\mathrm{题}\mathrm{符}\mathrm{号}\\ \overline{h}((\mathrm{\neg }\alpha ))=3+\overline{h}(\alpha )\\ \overline{h}((\alpha \circ \beta ))=3+\overline{h}(\alpha )+\overline{h}(\beta )\end{array}$$

递归定理的证明

递归定理的证明比较复杂，有时间再补充。