归纳与递归(Induction and Recursion)

归纳系统 (induction system)

在学完数学归纳法和语句归纳法后，实际上我们可以考虑抽象出归纳的概念.

对于每个自然数 $n$ ，都有一个性质 $\mathcal{P}$ ，可以记为 $\mathcal{P}(n)$ ，归纳假设实际上就是对于一个固定的 $n$ ，$\mathcal{P}(n)$ 成立时，可以推导出 $\mathcal{P}(n+1)$ .

此时我们记

\[ Y_{\mathcal{P}} = \left\lbrace n \in \omega : \mathcal{P}(n) \right\rbrace \]

（注意 $\omega$ 为自然数集）
归纳步骤实质上就是证明 $Y_{\mathcal{P}}$ 是封闭的. 最终的结论就是 $Y_{\mathcal{P}}=\omega$ .

对于语句归纳法，原子语句情形就是广义的 $0$ 的情形，而后继函数也类似，考虑利用集合的语言来进行概括.

定义：归纳系统 (Induction System)

一个归纳系统就是一个三元组 $\mathcal{X}=(X,X_0,\mathcal{H})$ ，其中 $X$ 为非空集合，$X_0 \subset X$ 且 $\mathcal{H}$ 为 $X$ 上的有限函数集合.

有限函数是指，对于每个 $H \in \mathcal{H}$ ，$H$ 为 $X^{k_H}\to X$ 的函数.

对于一个归纳系统，我们将其与一个集合序列关联，这个集合序列递推定义为：
$$ X_{n+1} := X_n \cup \left\lbrace H(x_0,\cdots,x_{k_H-1}):H\in \mathcal{H} \text{ and } x_0,\cdots,x_{k_H-1}\in X_n \right\rbrace $$
集合 $\overline{X} := \bigcup\limits_{n\in \omega}X_n$ 称为 $X_0$ 在 $\mathcal{H}$ 下的归纳闭包. 整个归纳过程称为集合 $\overline{X}$ 的归纳定义.

我们把原来的归纳法纳入到这个框架当中：对于自然数集合 $\omega$ ，构造归纳系统：

\[ \mathcal{X}_\omega = (\mathbb{R},\left\lbrace 0 \right\rbrace,\left\lbrace \mathrm{Sc} \right\rbrace) \]

其中 $\mathbb{R}$ 为实数集，而 $\mathrm{Sc}$ 为后继函数，即 $\mathrm{Sc}(n)=n+1$ .

那么不难推得：

\[ X_n = \left\lbrace 0,1,\cdots,n-1 \right\rbrace \]

归纳闭包自然就是 $\overline{X} = \omega$ .

命题：归纳集合的可数性

对任意的归纳系统 $\mathcal{X} = (X,X_0,\mathcal{H})$ ，如果 $X_0$ 和 $\mathcal{H}$ 是可数的，则归纳闭包 $\overline{X}$ 也是可数的.

可数集的并都是可数的，证明 $X_n$ 都可数即可. $\square$

归纳与递归(Induction and Recursion)

归纳系统 (induction system)

评论